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

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

• In what context? These normal forms are often helpful to prove results on context-free languages, but I'm not sure they have any practical currency. – Yuval Filmus Oct 19 '13 at 20:11

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.

• Thanks a lot for the comment. However, I wanted to know the advantage of GNF over the CNF. Any specific usage of GNF where CNF can not be used. – Sanjay Singh Oct 22 '13 at 10:34
• Related. cs.stackexchange.com/questions/10468/… . Converting to Greibach normal form seems to enable easier PDA construction, not totally sure yet tho. – Lance Pollard Jun 6 '15 at 3:53