chomsky normal form

Question

why do we convert the grammar to chomsky normal form ? Is there a advantage ?

Answer 1

For one thing, you can use the CYK algorithm on Chomsky Normal Form grammars

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

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!