Q1. [25] For S = {a, b}, construct the minimal DFA that accept the language consisting of
1) [8] all strings with an even number of a’s and an odd number of b’s.
2) [8] every ‘aa’ is followed immediately by a ‘b’. For example, the strings aab, aaba, aabaabbaab are in the language, but aaab and aabaa are not. Construct a DFA with 4 states.
3) [9] L = {w | ( na(w) – nb(w) ) mod 3 = 0 }. Construct a DFA with 3 states.
Q2. [10] Show that the language L = { an | n ³ 0, n ¹ 3 } is regular.
Q3. [15] For the language L = {an | n ³ 1 } È {bmak | m ³ 0, k ³ 0}
1) [8] Construct an NFA with three states that accepts L.
2) [7] Can you construct an NFA with the fewer states that accepts L? If so, construct it; otherwise, justify why your NFA in 1) is the minimal NFA.
a. No, it cannot be constructed in 2 states.
Q4. [20] For a given NFA in the figure,
1) [10] Give a language L that is accepted by the NFA. Describe L in the proper mathematical format, not in the verbal English description. E.g.) L = { an | n ³ 0, n ¹ 3 }
a. L = an | n = 3 OR n ≥ 2k, k ≥ 1
2) [10] Find a DFA that accepts the complement of the language defined by the NFA, i.e. .
a. L = {an | a ≠ 3 AND n ≥ 2k +1, k ≥ 0
Q5. [10] Construct an NFA with the minimum number of states that accepts
L = { an | n ³ 0 } È { bna | n ³ 1 }.
Q6. [10] Convert the NFA defined by the transitions below with the initial state q0 and the final state q2 into an equivalent DFA. Draw the transition graph of the DFA.
d(q0, a) = { q0, q1 }, d(q1, b) = { q1, q2 }, d(q2, a) = { q2 }, d(q1, l) = { q1, q2 }.
Q7. [20] For a given language, L = { anb | n ³ 1 } È { bna | n ³ 1},
(1) [10] Construct a minimal DFA with the minimum number of states that accepts L.
(2) [10] Prove that your DFA in 1) is minimal. Hint: Check if any pair of the states are indistinguishable to be merged in the same class so that the number of states are minimized
Q8. [10, optional] Prove or disprove the following conjecture: If L is regular, so is LR.
If it is true, construct a NFA MR s.t. L(M’) = LR , from a NFA M that accepts L, i.e. L(M) = L. Then, show that L(M’ ) = LR .
Otherwise, give a counter example.
