Da PDA a CFG

Massimo Caliman

1 min read 01/04/2018

Categories

• computer-science

Tags

• PDA
• CF
• CFG

Languages

• Italian

Kleeneliness is next to Gödeliness

Partiremo dall’assunto che valgano le seguenti due affermazioni.

• Da un PDA è sempre possibile costruire una CFG equivalente.
• Per un PDA aumentando i simboli nella pila di è possibile ridurre l’automa ad uno con un solo stato (Dato un PDA M ∃ PDA M’ con Q={q} : L(M)=L(M’), cioè un PDA equivalente con unico stato in grado di riconoscere lo stesso linguaggio)

Quindi per la costruzione della grammatica libera dal contesto equivalente partiamo da una prima fase di semplificazione dell’automa a pila, rendendolo un automa con un unico stato.

Possiamo costruire la CGF G=<T,N,P,S> equivalente al PDA M=<{q},Σ,Γ,δ,q,Z> con il seguente procedimento.

1. T=Σ l’alfabeto dei simboli del PDA diventa l’insieme dei terminali della CFG
2. N=Γ l’alfabeto della pila del PDA diventa l’insieme dei non terminali della CFG
3. S=Z il simbolo iniziale della pila del PDA diventa l’assioma della grammatica.
4. Una produzione p∈P
   1. X::=σγ sse <q,γ>∈δ(q,σ,X)
   2. X::=γZ sse <q,γ>∈δ(q,ε,X)

Più semplicemente passando in rassegna tutte le transizioni dell’automa

• se <q,σX> -> <q,γ> allora aggiungiamo X::=σγ alle produzioni di G
• se <q,εX> -> <q,γ> allora aggiungiamo X::=γZ alle produzioni di G

Segue che ∀u∈Σ, < q,u,Z > → <q, ε, ε> sse Z→*u ¹

1. Si può provare per induzione. ↩