## Description

Q1. [25] For S = {a, b}, construct the minimal DFA that accept the language consisting of

- all strings with an even number of
*a*’s and an odd number of*b*’s. - every ‘
*aa’*is followed immediately by a ‘*b’*. For example, the strings*aa**b*,*aa**b**a*,*aa**b**aa**b**b**aa**b*are in the language, but*aaab*and*aabaa*are not. Construct a DFA with 4 states. - L = {w | (
*n*(_{a}*w*) –*n*(_{b}*w*) ) mod 3 = 0 }. Construct a DFA with 3 states.

Q2. Show that the language L = { *a^{n} *|

*n*³ 0,

*n*¹ 3 } is regular.

Q3. For the language L = {*a ^{n}* |

*n*³ 1 } È {

*b*|

^{m}a^{k}*m*³ 0,

*k*³ 0}

- Construct an NFA with three states that accepts L.
- 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.

Q4. For a given NFA in the figure,

- Give a language
*L*that is accepted by the NFA. Describe L in the proper mathematical format, not in the verbal English description. g.) L = {*a*|^{n}*n*³ 0,*n*¹ 3 } - Find a
*DFA*that accepts theof the language defined by the NFA, i.e. .*complement*

Q5. Construct an NFA with the ** minimum** number of states that accepts

*L* = {* a ^{n}* |

*n*³ 0 } È {

*b*|

^{n}a*n*³ 1 }.

Q6. Convert the NFA defined by the transitions below with the initial state *q _{0}* and the final state

*q*into an

_{2}*equivalent DFA*. Draw the transition graph of the DFA.

d(*q _{0}, a*) = {

*q*}, d(

_{0}, q_{1 }*q*) = {

_{1}, b*q*}, d(

_{1}, q_{2 }*q*) = {

_{2}, a*q*}, d(

_{2 }*q*l) = {

_{1},*q*}.

_{1}, q_{2 }Q7. For a given language, L = { *a ^{n}b* |

*n*³ 1 } È {

*b*|

^{n}a*n*³ 1},

- Construct a
*minimal DFA*with the minimum number of states that accepts L. - 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. Prove or disprove the following conjecture: If L is regular, so is L^{R}.

If it is true, construct a NFA M^{R} s.t. L(M’) = L^{R} , from a NFA M that accepts L, i.e. L(M) = L. Then, show that L(M’ ) = L^{R }.

Otherwise, give a counter example.