1. Give the state diagrams of DFAs recognizing the following languages (S={a,b}):
L = {w | w contains at least four bs and at most one a}
2. Design an NFA for the following language over an alphabet S = {0,1,2}:
L = { y2z | y, z Î {0, 1}, the last symbols of both y and z are 1, and both y and z contain 010 as substring}
3. Given two regular languages L1 and L2 over an alphabet S = {0,1,2}, prove or disprove that the following languages are regular:
a. L but w Ï L2 }
b. L | w is in exactly one of L1 and L2 }
4. Convert the following NFA to an equivalent DFA following the steps described in class (see Theorem 1.39 in Sipser).
5. Convert the following DFA to an equivalent regular expression following the steps described in class (see Lemma 1.60 in Sipser).
6. Convert the regular expression (0+(11*))(01)* to an equivalent NFA following the steps described in class (see Lemma 1.55 in Sipser).
7. Over the alphabet S={a,b}, prove or disprove that the language {w|w contains equal number of substrings ab and ba} is a regular language.
8. Prove that the following language is not a regular language: L = { 0x1y | x, y ³ 1, (x ³ y) or (x < y and y modulus x = 0)
9. Write the context-free grammars which generate the following language:
a. 𝐿! = {𝑤 ∈ {𝑎, 𝑏}∗ | 𝑡he middle symbol of 𝑤 is 𝑏 and the length of 𝑤 is odd}
b. 𝐿# & | 𝑎, 𝑏, 𝑐 ≥ 0 and 𝑎 + 2𝑏 = 𝑐 }
