\begin{slide}{Sprachen von Keller-Automaten}


Übergangsrelation $(w, z, k) \to_A (w', z', u' k')$, falls

\begin{itemize}
\item $w = x w'$ für $x \in \Sigma$
  und $k = y k'$
  und $(z', u') \in T(x, z, y)$
\item \emph{oder} $w = w'$ 
  und $k = y k'$
  und $(z', u') \in T(\epsilon, z, y)$
\end{itemize}

akzeptierte Sprachen:
\begin{itemize}
\item
die durch leeren Keller akzeptierte Sprache:
$L_K(A) 
= \{ w \mid \exists z: (w, z_0, [y_0]) \to^* (\epsilon, z, \epsilon) \} $
 \item 
die durch Endzustandsmenge $F$ akzeptierte Sprache:
$L_F(A)
= \{ w \mid \exists z \in F, k \in Y^*: 
(w, z_0, [y_0]) \to^* (\epsilon, z, k) \} $
\end{itemize}
(Beachte in beiden Fällen: $\epsilon$-Übergänge sind noch möglich.)

\end{slide}

\begin{slide}{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$)

\begin{tabular}{l|l}
Grammatik & $\Rightarrow$ Automat \\ \hline
& nur ein Zustand $z_0$ \\
& Akzeptanz durch leeren Keller \\
Variablen $\cup$ Terminale & $=$ Kelleralphabet \\
Startsymbol & $=$ Startsymbol (im Keller) \\
Regel $X \to w$ 
& Regel $(\epsilon,z_0,X, z_0, w)$ \\
jedes $x \in \Sigma$ & Regel $(x, z_0, x, z_0, \epsilon)$. \\ \hline
\end{tabular}



Invariante (während der Rechnung):

(verbrauchter Teil der Eingabe $\circ$ Kellerinhalt) \\
ist aus Startsymbol ableitbar.


\end{slide}
