Encyclopedia > Greibach normal form

  Article Content

Greibach normal form

A context-free grammar is in Greibach normal form (GNF) iff all production rules are of the form:
A -> αX
where A is a nonterminal symbol, α is a terminal symbol and X is (possibly empty) sequence of nonterminal symbols.

No grammar in GNF can generate the null string. Conversely, every context-free grammar which does not generate the null string can be transformed into an equivalent grammar in Greibach normal form. This can be used to prove that every context-free language can be accepted by a non-deterministic pushdown automaton.



All Wikipedia text is available under the terms of the GNU Free Documentation License

 
  Search Encyclopedia

Search over one million articles, find something about almost anything!
 
 
  
  Featured Article
Ocean Beach, New York

... average household size is 2.26 and the average family size is 2.91. In the village the population is spread out with 21.7% under the age of 18, 5.1% from 18 to 24, 32.6% ...

 
 
 
This page was created in 38.8 ms