LARA

Chomsky Normal Form

A grammar is in Chomsky normal form if it has only these kinds of productions:

X ::= Y Z
X ::= t
S ::= ""

where

  • X,Y,Z denote non-terminals
  • t denotes terminals
  • S is the start non-terminal
  • if S::=“” appears, then S does not appear on right-hand side of another rule

Observe:

  • the empty string can only occur for the start non-terminal
  • terminals occur only by themselves on right-hand side
  • in parse tree, each non-terminal leads either to terminal or to two other non-terminals