Satz: Für alle Sprachen L gilt:
CFG G mit L(G) = L
Kellerautomat A mit L(A) = L.
Beweis (
)
- nur ein Zustand z0
- Variablenmenge = Kelleralphabet
- Startsymbol = Startsymbol (im Keller)
- Regel Bw = Übergang
(w, z0, Bk')(w, z0, wk')
- jedes Terminalzeichen
x :
Übergang
(xw', z0, xk')(w', z0, k').
Johannes Waldmann
2005-01-28