What is the advantage of Greibach Normal Form over Chomsky Normal Form?

Question

I wanted to know the pros and cons of Chomsky normal form and Greibach normal form.

Answer 1

There are actually several variants for these normal forms, so it might be useful to first recall the definitions. A context-free grammar is in Chomsky normal form if all of its production rules are of the form:

1. $X \to YZ$
2. $X \to a$
3. $S \to 1$

where $X, Y$ and $Z$ are nonterminal symbols, $S$ is the start symbol, $a$ is a letter and $1$ is the empty word. A grammar is in Chomsky reduced form if its productions are of the form 1 or 2, but with $X$ and $Y$ being possibly equal to the start symbol. The Chomsky Normal Form has been used to give a polynomial-time parsing algorithm (the CYK algorithm).

A grammar is in Greibach normal form if its productions are of the form

1. $X \to aX_1 \dotsm X_k$
2. $X \to b$

where $X, X_1, \dots, X_k$ are nonterminal symbols and $a$, $b$ are letters. It is in Greibach quadratic normal form if $k \leqslant 2$ in all rules. It is in Greibach two sided normal form if its productions are of the form

1. $X \to aX_1 \dotsm X_kb$
2. $X \to c$

where $X, X_1, \dots, X_k$ are nonterminal symbols and $a$, $b$, $c$ are letters. It is in Greibach quadratic two sided normal form (or Hotz normal form) if $k \leqslant 2$ in all rules. These normal forms have important applications in formal language theory. See for instance the article Towards an algebraic theory of context-free languages.