Massimo Caliman
Massimo Caliman
~1 min read

Categories

  • Theoretical Computer Science

Tags

  • PDA
  • CF
  • CFG

Languages

  • Italian

Kleeneliness is next to Gödeliness

Assumiamo che valga la seguente affermazione

  • Una CFG può essere ridotta in forma normale di Greibach.

Costruiamo il PDA M equivalente alla CFG G trasformata in forma normale di Greibach così

  1. Q={q}
  2. Σ=T
  3. Γ=N
  4. Z=S
  5. <q,γ>∈δ(q,σX) sse X::=σγ è una produzione di G

In pratica, una volta trasformata in forma normale di Greibach la nostra grammatica G e detta G’=<T,N,P,S> quest’ultima, l’automa a pila equivalente M è M=<{q},T,N,δ,q,S> dove δ è costuita transazione per transazione partendo da ogni singola produzione secondo la regola del punto 5. ovvero per ogni produzione che avrà necessariamente la forma X::=σγ creo costruisco una transazione <q,γ>∈δ(q,σX) cioè (q,σX) -> <q,γ>

Segue che ∀u∈Σ * , S->* u sse <q,u,S> ->* <q, ε, ε> 1

  1. Si può provare per induzione.