1.

Design DFAs to accept the following languages over the alphabet {a, b}.

Show the DFAs in terms of their transition diagrams. Clearly indicate the initial state, the accepting states, and the transitions following the conventions

L1 is the language of all strings in which every a is immediately preceded by a b

L2 is the language of all strings that begin with ab and end with ba.

L3 is the language of all strings that contain baa as a substring

L4 is the language of all strings that have an odd number of as and an even number of bs.

L5 is the language of all strings that contain neither aa nor bb as substrings.

2.

a)Construct an NFA M over the alphabet {a, b} such that the language accepted by M consists of strings in which the second to last symbol is b. Make sure M exhibits the two features that a DFA cannot exhibit. Show the transition diagram of your NFA

b)Show a successful execution sequence for the input string ababb. You can give your result by writing an alternating sequence of states and input symbols so that it represents a sequence of transitions of M.

c)Show 3 unsuccessful executions of M on the input bbababa.