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

Question

https://en.wikipedia.org/wiki/Chomsky_normal_form#Chomsky_reduced_form says

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$?

https://en.wikipedia.org/wiki/Greibach_normal_form says

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.

Answer 1

The definition of Chomsky normal form means exactly what it says: the lefthand side of each production must be a single non-terminal symbol, and the righthand side must be either a string of exactly two non-terminal symbols or a single terminal symbol. These restrictions do matter: because the types of production are so tightly restricted, it is much easier to reason about derivations from such a grammar and thus to prove theorems about context-free languages. In practical terms it allows parsers to use binary trees, and the exact lengths of derivations are known.

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.