Greibach normal form
Greibach normal form A restricted type of context-free grammar, namely one in which all productions have the form A → bC1…Cn
i.e. each right-hand side consists of a terminal followed by (zero or more) nonterminals. Any context-free language is generated by such a grammar, except that derivation of the empty string, Λ, requires the additional production S → Λ
One significance of this form is that it makes clear the existence of an equivalent pushdown automaton: on reading b the PDA can pop A from the stack and push C1…Cn.
i.e. each right-hand side consists of a terminal followed by (zero or more) nonterminals. Any context-free language is generated by such a grammar, except that derivation of the empty string, Λ, requires the additional production S → Λ
One significance of this form is that it makes clear the existence of an equivalent pushdown automaton: on reading b the PDA can pop A from the stack and push C1…Cn.
More From encyclopedia.com
You Might Also Like
NEARBY TERMS
Greibach normal form