Massimo Caliman
by Massimo Caliman
~1 min read


  • Programming


  • Context-Free Grammar
  • Pushdown Automata

Kleeneliness is next to Gödeliness

Let us assume that the following statement applies

  • A CFG can be reduced to Greibach normal form.

We construct the PDA M equivalent to the CFG G transformed to Greibach normal form as follows

  1. Q={q}
  2. Σ=T
  3. Γ=N
  4. Z=S
  5. <q,γ>∈δ(q,σX) sse X::=σγ is a production of G

In practice, once we have transformed our grammar G into Greibach normal form and called G’=<T,N,P,S> the latter, the equivalent stack automaton M is M=<{q},T,N,δ,q,S> where δ is constructed transaction by transaction starting with each individual production according to the rule in step 5. i.e. for each production that will necessarily have the form X::=σγ I create I construct a transaction <q,γ>∈δ(q,σX) i.e. (q,σX) -> <q,γ>

It follows that ∀u∈Σ * , S->* u sse <q,u,S> ->* <q, ε, ε> 1

  1. It can be proved by induction.