# What are the gists of CNF and GNF of CFG's?

A formal grammar is in Chomsky reduced form if all of its production rules are of the form: $$A\rightarrow \,BC$$ or $$A\rightarrow \,a$$ where $$A, B$$ and $$C$$ are nonterminal symbols, and $$a$$ is a terminal symbol.

• Is the gist of Chomsky normal form that the right hand side of each rule can't be a string that mixes both terminal symbols and variables?

• Do the number of terminal symbols and number of variables on the RHS of a rule matter? Is it material that CNF disallows $$A\rightarrow \,BCD$$ and $$A\rightarrow \,ab$$?

a context-free grammar is in Greibach normal form, if all production rules are of the form: $$A\to aA_{1}A_{2}\cdots A_{n}$$ or $$S\to \varepsilon$$ where $$A$$ is a nonterminal symbol, $$a$$ is a terminal symbol, $$A_{1}A_{2}\ldots A_{n}$$ is a (possibly empty) sequence of nonterminal symbols not including the start symbol, $$S$$ is the start symbol, and $$ε$$ is the empty word.

• Is the gist of GNF that the RHS of each rule must have terminal symbol at left and string of variables on the right, and no other orders between terminal symbol and variables are allowed?

• Does the number of terminal symbols on the RHS of each rule matter? Is it material that GNF disallows $$A\to abA_{1}A_{2}\cdots A_{n}$$?

Thanks.

Yes, apart from $$S\to\varepsilon$$ all productions of a grammar in Greibach normal form must have a righthand side that consists of a single terminal symbol followed by a string of zero or more non-terminal symbols. The fact that only a single terminal symbol is allowed is technically trivial, since a production $$A\to abcBC$$ is easily converted to $$A\to aX$$, $$X\to bY$$, and $$Y\to cBC$$, where $$X$$ and $$Y$$ are new non-terminal symbols, but it simplifies the theory and, for instance, makes the conversion to a pushdown automaton a mechanical task.