Science Fair Project Encyclopedia
Greibach normal form
In computer science, to 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
03-10-2013 05:06:04
The contents of this article is licensed from www.wikipedia.org under the GNU Free Documentation License. Click here to see the transparent copy and copyright details
The contents of this article is licensed from www.wikipedia.org under the GNU Free Documentation License. Click here to see the transparent copy and copyright details