Keller-Automaten-Sprachen und CFG

Satz: Für alle Sprachen L gilt: $\exists$ CFG G mit L(G) = L

$\iff$ $\exists$ Kellerautomat A mit L(A) = L.

Beweis ( $\Rightarrow$ )

Grammatik $\Rightarrow$ Automat

nur ein Zustand z₀

Akzeptanz durch leeren Keller

Variablen $\cup$ Terminale = Kelleralphabet

Startsymbol = Startsymbol (im Keller)

Regel X $\to$ w Regel ( $\epsilon$ , z₀, X, z₀, w)

jedes x $\in$ $\Sigma$ Regel (x, z₀, x, z₀, $\epsilon$ ).

Invariante (während der Rechnung):

(verbrauchter Teil der Eingabe o Kellerinhalt)
ist aus Startsymbol ableitbar.

Johannes Waldmann 2008-01-24

Grammatik	$\Rightarrow$ Automat
	nur ein Zustand z₀
	Akzeptanz durch leeren Keller
Variablen $\cup$ Terminale	= Kelleralphabet
Startsymbol	= Startsymbol (im Keller)
Regel X $\to$ w	Regel ( $\epsilon$ , z₀, X, z₀, w)
jedes x $\in$ $\Sigma$	Regel (x, z₀, x, z₀, $\epsilon$ ).