1.  Let  7 be any language.   We define  70  =  {reverse(x)|x 2  7}.   (For example,  if 7 = {q, qee, eeeqq, eeqqe}, then 70 = {q, eeq, qqeee, eqqee}.)

(a)  Prove that for any language 7, if there is an FA that accepts 7, then there is a TG that accepts 70.

(b)  Prove that for any language 7, if there is a TG that accepts 7, then there is a TG that accepts 70 .

2.  Consider  FA (iii) and  FA (iv)  on the  last page  of this  assignment.  Let  73  be  the language accepted by FA (iii), and let 74 be the language accepted by FA (iv).

(a)  Using the algorithm of Kleene’s theorem, Lemma 3, Rule 2, construct an FA for the union language 73 + 74 .

(b)  Give an example of a word in the language 73 +74 that is also in both languages 73 and 74.

(c)  Give a word in the language 73 + 74  that is also in 73, but not in 74 .

(d)  Give a word in the language 73 + 74  that is also in 74, but not in 73 .

3.  Consider Mealy machine below.

(a) Describe (in English phrases) what this Mealy machine is computing. (b) Convert this Mealy machine into a Moore machine.

(c) For input baba, what is the output of the original Mealy machine?

(d) For input baba, what is the output of your Moore machine.