 by Massimo Caliman

• English

### Categories

• Theoretical Computer Science

### Tags

• Context-Free Grammar
• Pushdown Automata

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]