AUTOMATA HOMEWORK
$10-15 USD
Paid on delivery
1) Reduce the following grammar into CNF.S -> ABS | AA | A | εA-> aAb | aBb | BB-> Bb | ε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 Є {a, b, c}*: #a(w) < #b(w) and #c(w) < #b(w)}
## Deliverables
in a word document
## Platform
windows xp
Project ID: #3451024