Description
Question 1 (45 pts)
:
q2
q0 q4 q3
q1 q5
b
b
a
b
a
a
b
a
b b
a
a
Figure 1. M1
1. Using the state minimization algorithm you have learned, find and draw the minimal DFA that is
equivalent to M1. Show each step of your solution clearly.
2. Define each equivalence class of the automaton you have found at part-a with regular expressions.
Hint&Remark: In your regular expressions, you are allowed to use the symbol L to denote all
strings recognized by the automaton (e.g. [ϵ] = Lbaa).
3. Use MyHill-Nerode Theorem to prove that the language
L
′ = {a
n
b
mc
kd
u
: m + n = k + 2u and m, n, k, u ∈ N} is not regular.
Question 2 (33 pts)
Give context-free grammars generating the following languages:
1. The strings over the alphabet {a, b} with more b
′
s than a
′
s.
2. A = {0
i1
j2
k
| i + k = j and i, j, k ≥ 0}
3. B = {w | the length of w is odd and w ∈ {0, 1}
∗} and draw parse tree for string 0011100.
Question 3 (22 pts)
Give the (context-free) languages generated by each of the given grammars:
1. 1. G1 = (V1, Σ, R1, S1) where V1 = {S1, A} ∪ Σ, Σ = {0, 1} and
R1 = {S1 −> 0A0 | 1A1 | e
A −> 0A | 1A | e }
2. G2 = (V2, Σ, R2, S2) where V2 = {S2, B} ∪ Σ, Σ = {0, 1} and
R2 = {S2 −> B1B1B
B −> 0B | 1B | e }
2
