A:B:

Let ={a,b}. Write a regular expression that generates precisely those words over that contain at most 1 non-overlapping occurrences of the (contiguous) subword baa . Examples: - babab contains 1 non-overlapping occurrences of bab: babab or babab - bababab contains 2 non-overlapping occurrences of bab: bababab The regular expressions have the following syntax: - for union, for concatenation and for Kleene star - or for , the language containing only the empty word - 0 (zero) for , the empty language - can often be left out Example expression: abcd(a+L+Obc)c is short for abcd(a++bc)c. NFA to Regular Expression Translate the automaton below into a regular expression using the algorithm described above. Note that the automaton already has a single initial and a single final state. Please draw the automaton after each step. Here a step consists of: - Removing all double arrows in the automaton. - Removing one state. - Again, remove all double arrows. It is important to follow the algorithm closely. The regular expressions have the following syntax: - for union, for concatenation and for Kleene star - or for , the language containing only the empty word - (zero) for , the empty language - can often be left out Example expression: abcd(a+L+0bc)c is short for abcd(a++bc)c