I have attached it's about theory of computation

Theory of Computation (CS 320)

Homework #3

Due: Sept. 21, 2016

Instructions:

· Have your written solutions ready at the beginning of class. Only if you cannot attend class, please e-mail your solutions to the instructor at [email protected] before 6:30 p.m. on the date due.

· You are allowed – and even encouraged - to work with other students, as well as to use textbooks and resources from the Internet, to solve these problems. However, your write-up must be your own and you must understand your answers. Inability to explain what you have written may result in losing credit for the homework assignment, and is likely to also result in poor performance on the exam.

Maximum score: 60 points

(Note: in the context of a regular expression, + denotes or/union)

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.