Description
- 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}
- 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}
- Given two regular languages L1 and L2 over an alphabet S = {0,1,2}, prove or disprove that the following languages are regular:
- L but w Ï L2 }
- L | w is in exactly one of L1 and L2 }
- Convert the following NFA to an equivalent DFA following the steps described in class (see Theorem 1.39 in Sipser).
- Convert the following DFA to an equivalent regular expression following the steps described in class (see Lemma 1.60 in Sipser).
- Convert the regular expression (0+(11*))(01)* to an equivalent NFA following the steps described in class (see Lemma 1.55 in Sipser).
- 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.
- 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)
- Write the context-free grammars which generate the following language:
- 𝐿! = {𝑤 ∈ {𝑎, 𝑏}∗ | 𝑡he middle symbol of 𝑤 is 𝑏 and the length of 𝑤 is odd}
- 𝐿# & | 𝑎, 𝑏, 𝑐 ≥ 0 and 𝑎 + 2𝑏 = 𝑐 }