[SOLVED] CSCI435-Assignment 2

Description

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

• [10] L = {aⁿb^m | (n+m) is odd}.

(aa)*(bb*) – a(aa)*b(bb*)

• [10, optional] L = {w Î {a, b}* | ( n_a(w) – n_b(w) ) mod 3 = 0}.  Hint: Apply Th^m2. .

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

• [10] L(ab(a+ab)*(a+aa))
• [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.

• [10]

 

1. 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)

1. q1= q0 a + q1 ab => q1 = q0 a(ab)* (from Arden’s Theorem)
2. q0 = q1 b + q1 ab + e

 

Now, substituting equation (ii) into (i), we get

1. 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)

 

• [10]

 

1. q0 = q0 b + e (q0 = starting point )
2. q1 = q0 b + q2 b

iii. q2 = q0 b + q1 a

 

Solving equation i) using Arden’s Theorem we get,

1. q0 = e (b)* => q0 = (b)*

 

Substituting value of q0 in equation (ii) and (iii), we get:

1. 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}

• [10] L(aa*(ab+a)*)

S -> aA

A -> Aa|B

B -> abB|aB\(lambda)

aA, aaA, aaaA, aaaabB, aaaababB, aaaababaB, aaaababa

 

• [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