Greibach normal form

A formal grammar G=(Σ,N,P,σ) is said to be in Greibach normal form if every production has the following form:


where AN (a non-terminal symbol), aΣ (a terminal symbol), and WN* (a word over N).

A formal grammar in Greibach normal form is a context-free grammar. Moreover, any context-free language not containing the empty word λ can be generated by a grammar in Greibach normal form. And if a context-free language L contains λ, then L can be generated by a grammar that is in Greibach normal form, with the additionPlanetmathPlanetmath of the production σλ.

Let L be a context-free language not containing λ, and let G=(Σ,N,P,σ) be a grammar in Greibach normal form generating L. We construct a PDA M from G based on the following specifications:

  1. 1.

    M has one state p,

  2. 2.

    the input alphabet of M is Σ,

  3. 3.

    the stack alphabet of M is N,

  4. 4.

    the initial stack symbol of M is the start symbol σ of G,

  5. 5.

    the start state of M is the only state of M, namely p

  6. 6.

    there are no final states,

  7. 7.

    the transition function T of M takes (p,a,A) to the singleton {(p,W)}, provided that AaW is a production of G. Otherwise, T(p,a,A)=.

It can be shown that L=L(M), the languagePlanetmathPlanetmath accepted on empty stack, by M. If we further define T(p,λ,σ):={(p,λ)}, then M accepts L{λ}. As a result, any context-free language is accepted by some PDA.


Title Greibach normal form
Canonical name GreibachNormalForm
Date of creation 2013-03-22 18:55:22
Last modified on 2013-03-22 18:55:22
Owner CWoo (3771)
Last modified by CWoo (3771)
Numerical id 7
Author CWoo (3771)
Entry type Definition
Classification msc 68Q42
Classification msc 68Q45
Synonym GNF
Related topic ChomskyNormalForm
Related topic KurodaNormalForm