|
|
|
|
|
Greibach Normal FormTo say that a context-free grammar is in Greibach normal form (GNF) means that all production rules are of the form: -
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. Greibach normal form is named for Sheila Greibach. See also
|
 |
|
| Copyright 2005-2009 OnPedia.com. All Rights Reserved |
|
|