1. Let Σ = {a, b}.  For each of the languages below, give an example of a string in the language, and a string not in the language.

(a) L1 = {w e Σ* : w = uuR u, for some u e Σ2 }.

(b) L2 = {w e Σ* : ww = www}.

(c) L3 = {w e Σ* : uvw = wvu, for some {u, v} c Σ* }.

(d) L4 = {w e Σ* : www = uu, for some u e Σ* }.

2. Construct a DFA for each of the following languages

(a) All and only those strings over {a, b, c} whose symbols are in alphabetical order.  For

example, aaabcc and ac are to be accepted, and abca and cb should be rejected.

(b) All and only those strings over {0, 1} that have an even number of 0’s and the number of

1’s is a multiple of 3.

(c) L = {an bm ck  : n, m, k > 0, n + m + k is even }

(d) L2 = {w e {a, b}*  : w does not contain aab and w ends in bb}

3. Let L = {w e {0, 1}*   : w has an odd no. of 1’s }, and let A be the DFA with tabular represen- tation:

Prove that L = L(A). Hint: Do the L(A) s L part of the proof by induction on the the length of the string processed by A. You need a mutual induction with a claim for state p and a claim for state q .

4. Construct an NFA for the set of strings over alphabet {a, b, c} that have a substring of length 3 containing each of the symbols (in any order).