Q1. [10] Find all strings in L((ab + b)* b (a + ab)*) of length less than four.
b, ab, bb, ba, abb, bba, bbb, baa, bab
Q2. [10] Give a regular expression for the language
(1) [10] L = {anbm | (n+m) is odd}.
(aa)*(bb*) - a(aa)*b(bb*)
(2) [10, optional] L = {w Î {a, b}* | ( na(w) - nb(w) ) mod 3 = 0}. Hint: Apply Thm 3.2. .
RE = ((ab*(ab+b)(ba)*(bb+a)(ab)*)*
Q3. [10] Using the construction in Theorem 3.1, construct an NFA that accepts the complement of the
Language L(ab*aa + bba*ab).
Q4. [20] Construct a minimal DFA that accepts the following language
1) [10] L(ab(a+ab)*(a+aa))
2) [10] L((aa*)*b)*)
Hint: Start with constructing an NFA (by Theorem 3.1), convert it to DFA, then get the minimal DFA by mark & reduce procedures.
Q5. [20] Find regular expressions for the languages accepted by the following automaton.
1) [10]
i. q0 = q1 b + q2 b + e (e = epsilon & q0 = initial state)ii. q1 = q0 a + z3 b
iii. q2 = q1 a
Substituting eqn. (iii) in (i) and (ii)
ii. q1= q0 a + q1 ab = q1 = q0 a(ab)* (from Arden's Theorem)
i. q0 = q1 b + q1 ab + e
Now, substituting equation (ii) into (i), we get
i. q0 = e + q0 a (ab)* b + q0 a (ab)* ab
= q0 = e + q0 (a (ab)* (b + ab))
= q0 = e (a (ab)* (b + ab))
= q0 = a (ab)* (b + ab)
Thus, q0 = a (ab)* (b + ab)
2) [10]
i. q0 = q0 b + e (q0 = starting point )
ii. q1 = q0 b + q2 b
iii. q2 = q0 b + q1 a
Solving equation i) using Arden's Theorem we get,
i. q0 = e (b)* = q0 = (b)*
Substituting value of q0 in equation (ii) and (iii), we get:
ii. q1 = (b)* b + q2 b
iii. q2 = (b)* b + q1 a
Substituting equation (ii) in (iii), we get,
iii. q2 = (b)* b + ( (b)* b + q2 b ) a
= q2 = (b)*b + (b)* ba + z3 ba= q2 = ((b)*b + (b)* ba) (ba)* (using Arden's Theorem)
q1 = (b)* b + (((b)*b + (b)* ba) (ba)*) b
Q6. [10] Construct a DFA that accepts the language generated by the grammar
S ® abS | B, A ® aB | bb, B ® baA.
Q7. [20] Find a regular grammar that generates the language on S={a, b}
1) [10] L(aa*(ab+a)*)
S - aA
A - Aa|B
B - abB|aB\(lambda)
aA, aaA, aaaA, aaaabB, aaaababB, aaaababaB, aaaababa
2) [10] the language consisting of all strings with no more than two a’s.
b*a{0,1} b*a{0,1} b*
babab
aa
aba
bbb
