Massimo Caliman
by Massimo Caliman
1 min read

Categories

  • Programming

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.

  1. T=Σ the alphabet of symbols of the PDA becomes the set of terminals of the CFG.
  2. N=Γ the alphabet of the PDA stack becomes the set of non-terminals of the CFG.
  3. S=Z the initial symbol of the PDA stack becomes the axiom of the grammar.
  4. A p∈P production
    1. X::=σγ iff <q,γ>∈δ(q,σ,X)
    2. X::=γZ iff <q,γ>∈δ(q,ε,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]