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,γ>`then`

we add X::=σγ to the productions of G`if`

<q,εX> -> <q,γ>`then`

we add X::=γZ to the productions of G

It follows that ∀u∈Σ*, < q,u,Z > →* <q, ε, ε> `iff`

Z→*u [^footnote1]