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
- Q={q}
- Σ=T
- Γ=N
- Z=S
- <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
-
It can be proved by induction. ↩