The importance of normal forms like Chomsky normal form for CFGs

I understand that context-free grammars can be used to represent context-free languages.It might have ambiguities. We also have normal forms like Chomsky and Greibach normal form. I couldn't understand the need of that.

Why they are important in the theory of languages? All the textbooks I referred to tell about these normal forms but not telling anything about their importance.

• Normal forms are handy when giving constructive proofs. – Karolis Juodelė Mar 12 '13 at 7:53

There are at least two relevant uses.

1. Simplicity of proofs
There are plenty of proofs around context-free grammars, including reducability and equivalence to automata. Those are the simpler the more restricted the set of grammars you have to deal with is. Therefore, normal forms can be helpful there.

As a concrete example, Greibach normal form is used to show (constructively) that there is an $\varepsilon$-transition-free PDA for every CFL (that does not contain $\varepsilon$).

2. Enables parsing
While PDAs can be used to parse words with any grammar, this is often inconvenient. Normal forms can give us more structure to work with, resulting in easier parsing algorithms.

As a concrete example, the CYK algorithm uses Chomsky normal form. Greibach normal form, on the other hand, enables recursive-descent parsing; even though backtracking may be necessary, space complexity is linear.

Chomsky normal form enables a polynomial time algorithm to decide whether a string can be generated by a grammar. The algorithm is pretty slick if you know dynamic programming...

If the length of your input ($I$) is $n$ then you take a 2d array ($A$) of dim $n$x$n$.

$A[i,j]$ denotes all the symbols in the grammar $G$ that can derive the sub-string $I(i,j)$.

So finally if $A[1,n]$ contains the start symbol ($S$) then it means that the string I can be derived by $S$ which is what we wanted to check.

def decide (string s,grammar G):
//base case
for i=1 to n:
N[i,i]=I[i]    //as the substring of length one can be generated by only a
terminal.
//end base case

//induction
for s=1 to n:       //length of substring
for i=1 to n-s-1: //start index of substring
for j=i to i+s-1:   //something else
if there exists a rule A->BC such that B belongs to N[i,j] and C
belongs to N[j+1,i+s-1] then add A to N[i,i+s-1]
//endInduction

if S belongs to N[1,n] then accept else reject.


I know that the indexes seem pretty crazy. But basically here's whats happening.

• The base case is pretty clear I think.

• In the inductive step we build the solution for a length $s$ substring from all the solutions with length less than $s$.

• Say, you are finding the solution for length $5$ substring (sub) starting at index $1$. Then you start a loop (something else part).....which checks whether there is a rule ($A->BC$) such that $B$ and $C$ derive two contiguous and disjoint substrings of sub and if so add all such $A$'s to $N[1,6]$.

• Finally, if you have the start symbol in $N[1,n]$ then you accept!

• This is the CYK algorithm which a) you should name as such and b) has been mentioned in my answer. Note that polynomial runtime is only impressive because the algorithm is uniform over all CFGs, that is it is general. – Raphael Dec 5 '13 at 7:48
• @Raphael ok....i didn't know the name :) – ishan3243 Dec 6 '13 at 5:19

Sheila Greibach invented the Greibach normal form to prove that every CFG can be recognized by a PDA that works in real time (i.e., without $\epsilon$-transitions).