Theory of Computation Assignment
1. Find regular expressions for the following languages:
a. L = {an bm : n ≥ 3, m is odd}
b. L = {an bm : n + m is odd}
c. L = {w € {a, b}* : |w| mod 3 ≠ 0}
2. Let r1 and r2 denote regular expressions. Which of the following statements are true?
a. (r1*)* ≡ r1*
b. (r1*)( r1 + r2)* ≡ (r1 + r2)*
c. ( r1 + r2)* ≡ (r1* r2*)*
d. (r1 r2)* ≡ (r1* r2*)
3. Find NFA (with λ-transitions) that accepts the language corresponding to the regular expression ab*aa + bba*ab.
4. Find NFA (with λ-transitions) that accepts the language corresponding to the regular expression (a + b)* b (a + bb)*.
5. Recall that a "left-linear grammar" is a grammar in which all non-terminals (i.e. variables) are on the left end of the right side of production rules, while a "right-linear grammar" is a grammar in which all non-terminals (i.e. variables) are on the right end of the right side of production rules.
a. Find a left-linear grammar that generates L = {an bm : n ≥ 3, m ≥ 2}
b. Find a right-linear grammar that generates L = {an bm : n ≥ 3, m ≥ 2}
6. Recall that a "(right) regular grammar" is a right-linear grammar in which production rules belong to these three formats: A → λ (empty string); A → a (terminal alphabet symbol); A → aB (terminal followed by non-terminal). Find a regular grammar that generates all strings over {a, b} * with no more than two a's.