Overview

Greibach normal form


Related Overviews

 

'Greibach normal form' can also refer to...

 

More Like This

Show all results sharing this subject:

  • Computing

GO

Show Summary Details

Quick Reference

A restricted type of context-free grammar, namely one in which all productions have the form

AbC1Cn

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

C1Cn

.

Subjects: Computing.


Reference entries

Users without a subscription are not able to see the full content. Please, subscribe or login to access all content.