[SOLVED] CSCI435 Home Assignment 2

Q1. [10] Find all strings in L((ab + b)* b (a + ab)*) of length less than four.

Q2. [10] Give a regular expression for the language

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

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

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)*)
• [10] the language consisting of all strings with no more than two a’s.