I wanted to know the pros and cons of Chomsky normal form and Greibach normal form.
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:
- $X \to YZ$
- $X \to a$
- $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
- $X \to aX_1 \dotsm X_k$
- $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
- $X \to aX_1 \dotsm X_kb$
- $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.