chomsky normal form

why do we convert the grammar to chomsky normal form ? Is there a advantage ?开发者_运维问答

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

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!

For example, grammar in CNF (or rather its derivation tree) is used to prove pumping lemma for context-free languages.

Advantages of using Chomsky Normal Form are:

1. Simplicity of proof We have many proofs for context-free grammars, including reducability and equivalence to automata. But these are the simpler and the more restricted set of grammars have to dealth with.Therefore, normal forms are helpful. For example, Greibach normal form is used to show that there is an ε-transition-free PDA for every CFL (that does not contain ε).

2.Enables parsing The PDAs are used to parse words with any grammar, which is inconvenient. Normal forms give us more structure to work with, resulting in easier parsing algorithms.

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