Kleeneliness is next to Gödeliness
We will start from the assumption that the following two statements apply.
- It is always possible to construct an equivalent CFG from a PDA.
- For a PDA by increasing the symbols in the stack it is possible to reduce the automaton to one with only one state (Given a PDA M ∃ PDA M’ with Q={q} L(M)=L(M’), i.e. an equivalent PDA with only one state capable of recognising the same language)
So for the construction of the equivalent context-free grammar, we start with a first step of simplifying the stack automaton, making it a single-state automaton.
We can construct the CGF G=<T,N,P,S> equivalent to the PDA M=<{q},Σ,Γ,δ,q,Z> with the following procedure.
- T=Σ the alphabet of symbols of the PDA becomes the set of terminals of the CFG.
- N=Γ the alphabet of the PDA stack becomes the set of non-terminals of the CFG.
- S=Z the initial symbol of the PDA stack becomes the axiom of the grammar.
- A p∈P production
- X::=σγ
iff<q,γ>∈δ(q,σ,X) - X::=γZ
iff<q,γ>∈δ(q,ε,X)
- X::=σγ
More simply by reviewing all the transitions of the automaton
if<q,σX> -> <q,γ>thenwe add X::=σγ to the productions of Gif<q,εX> -> <q,γ>thenwe add X::=γZ to the productions of G
It follows that ∀u∈Σ, < q,u,Z > → <q, ε, ε> iff Z→*u [^footnote1]