%% This LaTeX-file was created by <tommy> Thu Sep 23 12:43:50 1999
%% LyX 1.0 (C) 1995-1999 by Matthias Ettrich and the LyX Team

%% Do not edit this file unless you know what you are doing.
\documentclass[a4paper,german]{article}
\usepackage[latin2]{inputenc}
\pagestyle{empty}
\usepackage{babel}
\IfFileExists{url.sty}{\usepackage{url}}{\let\url=\verb}

\makeatletter


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% LyX specific LaTeX commands.
\providecommand{\LyX}{L\kern-.1667em\lower.25em\hbox{Y}\kern-.125emX\@}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% Textclass specific LaTeX commands.
\newenvironment{lyxlist}[1]
  {\begin{list}{}
    {\settowidth{\labelwidth}{#1}
     \setlength{\leftmargin}{\labelwidth}
     \addtolength{\leftmargin}{\labelsep}
     \renewcommand{\makelabel}[1]{##1 \hfill}}}
  {\end{list}}
\newenvironment{lyxcode}
  {\begin{list}{}{
    \setlength{\rightmargin}{\leftmargin}
    \raggedright
    \setlength{\itemsep}{0pt}
    \setlength{\parsep}{0pt}
    \ttfamily}%
   \item[]}
  {\end{list}}

\makeatother

\begin{document}


\title{Kellerautomaten}


\author{Thomas Rabe}

\maketitle

\section*{Einleitung}

Dies ist eine Projektarbeit von Maik Martin und Thomas Rabe, die im Rahmen eines
Java-Praktikums stattfand. Dieser Text ist weder vollständig noch erhebt er
Anspruch auf Korrektheit!


\section*{Motivation}

Zu jedem regulärem Ausdruck existiert ein endlicher Automat, welcher die zugehörige
Sprache akzeptiert. Aufgrund der 'Trivialität' der regulären Sprachen sind die
Möglichkeiten dieser stark eingeschränkt. So ist z.B. die Sprache \( L=\{wc\overline{w}|w\in \{0,1\}^{*}\} \),
erzeugt durch die Grammatik \( G=(\{S\},\{0,1,c\},\{S\rightarrow 0S0|1S1|c\},S) \)
\textbf{nicht} regulär\footnote{%
Pumping-Lemma ;)
}. Diese Sprache ist kontextfrei und einen sie akzeptierenden Automat kann durch
Erweiterung des endlichen Automaten um einen zusätzlichen Speicher gebastelt
werden: Dem Automaten wird ein zusätzliches Band spendiert, allerdings mit der
Einschränkung das dieses nur als Stack benutzt wird. Desweiteren funktioniert
das Eingabeband als ROM, d.h. es kann nur gelesen werden. Im Gegensatz zu Regelsystemen,
die formale Sprachen als Wortmengen erzeugen können, ist der Kellerautomat ein
echter Ja/Nein-Sager: Zu einem gegebenen Wort, welches auf das Eingabeband geschrieben
wird, entscheidet der Automat mittels einer Überführungsfunktion, ob dieses
Wort zu der definierten Sprache gehört. Solche Systeme bezeichnet man als Akzeptoren.
Als Anwendungsgebiet dieser Sprachen ist vor allem die BACKUS-NOUR-FORM (BNF)
zu nennen, da diese vor allem bei der Syntaxdefinition von Programmiersprachen
verwendet wird.


\section*{Definition des Kellerautomaten}

Ein Kellerautomat ist ein Siebentupel \( KA=(Z,X,Y,\delta ,z_{0},y_{0},F) \)
mit

\begin{enumerate}
\item \( Z \) endliche Menge von Zuständen
\item \( X \) Eingabealphabet
\item \( Y \) Kelleralphabet
\item \( \delta  \) Überführungsfunktion
\item \( z_{0}\in Z \) Anfangszustand
\item \( y_{0}\in Y \) Kellerstartsymbol
\item \( F\subset Z \) Endzustände
\end{enumerate}
Die Überführungsfunktion \( \delta :Z\times (X\cup \{\epsilon \})\times Y\rightarrow 2^{Z\times Y^{*}} \)
ist nichtdeterministisch.


\section*{Arbeitsweise}


\subsection*{Bewegungen des Kellerautomaten}

Der Automat kann 2 Typen von Bewegungen ausführen:

\begin{itemize}
\item Das oberste Kellersymbol wird abhängig von Eingabe, Zustand und Keller geändert.
Der Lesekopf bewegt sich ein Zeichen nach rechts und es erfolgt ein Zustandswechsel.
\item \( \epsilon  \) -Bewegung: Keller und Zustand werden unabhängig von der Eingabe
verändert; der Lesekopf bewegt sich \textbf{nicht}.
\end{itemize}
\( \delta (z,x,y)=\{(z_{1},y_{1}),...,(z_{n},y_{n})\} \) bedeutet: Im Zustand
\( z \), bei Eingabezeichen \( x \) und oberstem Kellersymbol \( y \) bewegt
sich der Lesekopf um ein Zeichen nach rechts, wechselt in einen der Zustände
\( z_{i} \) und ersetzt \( y \) durch \( y_{i} \). Ist \( x=\epsilon  \),
bewegt sich der Lesekopf nicht.


\subsection*{Zustandsbeschreibungen (Konfigurationen)}

Eine Konfiguration \( k=(z,p,q) \) zu einer festen Zeit ist ein Tripel bestehend
aus Zustand \( z \), nicht verbrauchter Eingabe \( p \) und Kellerinhalt \( q \).
Zu jedem \( k \) existiert eine Folgekonfiguration \( k' \) (\( k\vdash k' \)).


\subsection*{Akzeptierte Sprachen}

Der Kellerautomat \( KA=(Z,X,Y,\delta ,z_{0},y_{0},F) \) kann auf 2 verschiedene
Arten eine Sprache akzeptieren:

\begin{enumerate}
\item Menge aller Sprachen, die zu leerem Keller führen: \( L_{\epsilon }(KA)=\{p|p\in X^{*} \)und
\( \exists z\in Z:(z_{0},p,y_{0})\vdash ^{*}(z,\epsilon \, \epsilon )\} \). 
\item Vom Kellerautomaten mit Endzustand akzeptierte Sprache: \( L_{f}(KA)=\{p|p\in X^{*}\wedge (z_{0},p,y_{0})\vdash ^{*}(z_{f},\epsilon \, q) \)
mit \( z_{f}\in F \) und \( q\in Y^{*}\} \).
\end{enumerate}
\begin{quote}
Bem: Zu jedem durch Endzustand akzeptierenden Kellerautomaten K existiert ein
K' der die Sprache durch leeren Keller akzeptiert und andersherum.
\end{quote}

\subsection*{deterministische und nichtdet. Kellerautomaten}

Ein nichtdeterministischer Kellerautomat akzeptiert mehr als ein det. KA. Es
gilt \( DKA\subset NKA \).

Beispiel: Die Menge aller Palindrome \( L=\{w\overline{w}|w\in (0+1)^{*}\} \)
wird von keinem DKA akzeptiert (keine Möglichkeit die Mitte des Palindroms zu
erraten).


\section*{Applet }

Zum starten bitte hier klicken: http://stinfwww.informatik.uni-leipzig.de/~mai97kgs/pda/bin/StartHier.html \url|PDA|


\subsection*{Arbeitsweise}

Um dieses Applet zu benutzen, muß ein File mit Überführungsfunktion, Eingabewort,
Kellersymbol erstellet werden. Einen extra Editor zu schreiben bzw. implementieren
erschien uns als unnötig, da der interessierte Anwender meistens sowieso ``seinen''
Editor benutzt. Außerdem liegen zum Spielen ein paar Automaten per Menu bereit.
Die Dateien werden wie folgt erstellt:

\begin{itemize}
\item Eine Zahl beschreibt den Startzustand S:
\end{itemize}
\begin{lyxcode}
S=0;
\end{lyxcode}
\begin{itemize}
\item Ein String (X) das Eingabewort:
\end{itemize}
\begin{lyxcode}
X=110011;
\end{lyxcode}
\begin{itemize}
\item Ein Character (Y) das Kellerstartsymbol:
\end{itemize}
\begin{lyxcode}
Y=a;
\end{lyxcode}
\begin{itemize}
\item Nun folgt die Überführungsfunktion: 
\end{itemize}
\begin{lyxcode}
Z:X:Y~=~z:y~\{,z:y\}
\end{lyxcode}
mit

\begin{lyxlist}{00.00.0000}
\item [Z]aktueller Zustand (Zahl)
\item [X]gelesenes Zeichen (Zahl oder Buchstabe)
\item [Y]oberstes Kellersymbol
\item [z]neuer Zustand
\item [y]neuer Kellerstring (Symbol kellern - Buchstabe, Keller nicht verändern -
'@', \( \epsilon  \) -Bewegung / Kellersymbol leeren - '\#'.
\end{lyxlist}
\end{document}