11
$\begingroup$

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.

$\endgroup$
  • 2
    $\begingroup$ Normal forms are handy when giving constructive proofs. $\endgroup$ – Karolis Juodelė Mar 12 '13 at 7:53
11
$\begingroup$

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.

$\endgroup$
4
$\begingroup$

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

$\endgroup$
4
$\begingroup$

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!

  • $\endgroup$
    • 3
      $\begingroup$ 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. $\endgroup$ – Raphael Dec 5 '13 at 7:48
    • $\begingroup$ @Raphael ok....i didn't know the name :) $\endgroup$ – ishan3243 Dec 6 '13 at 5:19

    Your Answer

    By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

    Not the answer you're looking for? Browse other questions tagged or ask your own question.