AUTOMATA HOMEWORK

1) Reduce the following grammar into CNF.S -> ABS | AA | A | &epsilon;A-> aAb | aBb | BB-> Bb | &epsilon;2) Let *G = (V,T,P,S)* be any CFG without *epsilon* productions or unit productions. Let *k* bethe maximum number of symbols on the right side of productions in *P*. Show that there is anequivalent grammar in Chomsky Normal Form with no more than *(k-1)|P| + |T|* productionrules. ( V is the set of variables, T the terminals, P the set of productions, and S the startsymbol)3) Prove that the following language is not context free using the context free pumpinglemma.L = {w &#1028; {a, b, c}*: #a(w) < #b(w) and #c(w) < #b(w)} ## Deliverables in a word document ## Platform windows xp