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ì
- Q={q}
- Σ=T
- Γ=N
- Z=S
- <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
-
Si può provare per induzione. ↩