The importance of normal forms like Chomsky normal form for CFGs

Question

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.

Answer 1

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.

Answer 2

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!

Answer 3

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).