4
$\begingroup$

I wanted to know the pros and cons of Chomsky normal form and Greibach normal form.

$\endgroup$
  • $\begingroup$ In what context? These normal forms are often helpful to prove results on context-free languages, but I'm not sure they have any practical currency. $\endgroup$ – Yuval Filmus Oct 19 '13 at 20:11
1
$\begingroup$

There are actually several variants for these normal forms, so it might be useful to first recall the definitions. A context-free grammar is in Chomsky normal form if all of its production rules are of the form:

  1. $X \to YZ$
  2. $X \to a$
  3. $S \to 1$

where $X, Y$ and $Z$ are nonterminal symbols, $S$ is the start symbol, $a$ is a letter and $1$ is the empty word. A grammar is in Chomsky reduced form if its productions are of the form 1 or 2, but with $X$ and $Y$ being possibly equal to the start symbol. The Chomsky Normal Form has been used to give a polynomial-time parsing algorithm (the CYK algorithm).

A grammar is in Greibach normal form if its productions are of the form

  1. $X \to aX_1 \dotsm X_k$
  2. $X \to b$

where $X, X_1, \dots, X_k$ are nonterminal symbols and $a$, $b$ are letters. It is in Greibach quadratic normal form if $k \leqslant 2$ in all rules. It is in Greibach two sided normal form if its productions are of the form

  1. $X \to aX_1 \dotsm X_kb$
  2. $X \to c$

where $X, X_1, \dots, X_k$ are nonterminal symbols and $a$, $b$, $c$ are letters. It is in Greibach quadratic two sided normal form (or Hotz normal form) if $k \leqslant 2$ in all rules. These normal forms have important applications in formal language theory. See for instance the article Towards an algebraic theory of context-free languages.

$\endgroup$
  • 1
    $\begingroup$ Thanks a lot for the comment. However, I wanted to know the advantage of GNF over the CNF. Any specific usage of GNF where CNF can not be used. $\endgroup$ – Sanjay Singh Oct 22 '13 at 10:34
  • $\begingroup$ Related. cs.stackexchange.com/questions/10468/… . Converting to Greibach normal form seems to enable easier PDA construction, not totally sure yet tho. $\endgroup$ – Lance Pollard Jun 6 '15 at 3:53

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.