AutoMata

1) Design (draw the diagram) a Moore machine that performs a parity check on the input string (string of 0 and 1): that is, the output string ends in 1 if the total number of 1-bits in the input string is odd and 0 if the total number of 1-bits in the input string is even (the front part of the output string is ignored). 2) For the following 1 2 regular language, find the regular expression and an FA that define L ÇL . L 12 = (a+b)b(a+b)*, L =b(a+b)* You need to draw the FAs first. Be sure to show all your work. 3) Prove that the languages accepted by the following FAs are equivalent (show your work). 4) Use the pumping lemma to prove the following language is nonregular: L = {a b } = {abb, aabbbb, aaabbbbbb, …} n 2n 5) Show the grammar is ambiguous: S® AB | aaB A® a | Aa B® b 6) Convert the following context-free grammar into Chomsky Normal Form. Show you work. S ® aXX X® aS | bS | a 7) Find CFGs that generate these regular languages over the alphabet Ó = {a, b} Draw a Finite Automata first and use this to create the CFG. (a) The language defined by (aa + bb)* (b) The set of all strings with exactly one a (and begins with a b) or exactly one b (and begins with an a). That is (bb ab + aa ba )