% 11. Uebungsblatt GTI SS 2005
\documentclass [11pt] {article}
%\usepackage [reqno] {amsmath}
\usepackage{amsfonts}
\usepackage {german}
\usepackage[latin1]{inputenc}
\textwidth=15,5cm
\textheight=25cm
%\textheight=26cm
\hoffset = -19mm
\voffset = -25mm
\let\eps=\varepsilon
\selectlanguage{ngerman}

\setcounter{page}{13}
\begin{document}

\begin{centering}
{\large \bf Grundlagen der  theoretischen Informatik, SS 2005 ---
 11.~\"Ubungsblatt\par
}
\medskip
freiwillige Abgabe bis Montag, 11. Juli 2005, 10:15 Uhr
\par \medskip
\end{centering}
\hrule
\medskip


\begin{enumerate}
\setcounter{enumi}{78}


\item
  \begin{enumerate}
  \item 
Wandeln Sie den folgenden Kellerautomaten
in einen äquivalenten Kellerautomaten mit nur einem einzigen Zustand um.
$\delta = \{
(q_0,0,\gamma\mid q_1, Z_0\gamma),\allowbreak
(q_0,1,\gamma\mid q_1, Z_1\gamma), \allowbreak
(q_1,0,\gamma\mid q_0, Z_0\gamma), \allowbreak
(q_1,1,\gamma\mid q_1, Z_1Z_1), \allowbreak
(q_0,1,Z_1\mid q_0, \eps),
(q_0,0,Z_0\mid q_0, \eps)\}$.
Dabei steht $\gamma$ jeweils für ein beliebiges Kellersymbol
$\gamma\in \Gamma=\{Z_0,Z_1\}$.
\item Konstruieren Sie eine entsprechende kontextfreie Grammatik.
  \end{enumerate}

\item
Beweisen Sie, dass die kontextfreien Sprachen abgeschlossen
gegenüber der Vereinigung mit regulären Sprachen sind.

% \item 
% Welche Beispiele von kontextfreien Sprachen kennen Sie, die keine
% deterministischen kontextfreien Sprachen sind?


\item 
\begin{enumerate} 
\item Erweitern Sie das Haskell-Programm aus der Vorlesung zur
  Simulation eines deterministischen Zweiweg-Kellerautomaten und zur
  Berechnung der Entladefunktion%
  \footnote{\tt
    http://www.inf.fu-berlin.de/lehre/SS05/GTI/2Weg-PDA-Teilwort.hs}
 so, dass es die Anzahl der Schritte
  ausgibt, die der Automat bis zum Leeren des Kellers macht.
\item Erweitern Sie das Programm so, dass es auch dann terminiert,
wenn der Automat in eine unendliche Schleife gerät.%
\footnote{\tt
http://www.inf.fu-berlin.de/lehre/SS05/GTI/2Weg-PDA-Zaehler.hs}
\end{enumerate}

\item
Betrachten Sie die deterministischen Zweiweg-Kellerautomaten
mit dem Eingabealphabet $\Sigma=\{a\}$, dem Kelleralphabet
$\Gamma=\{0,1,Z_0\}$
und der Übergangsfunktion $\delta\colon 
Q \times(\Sigma\cup\{\%,\$\}) \times \Gamma \to
 Q\times\Gamma^*\times \{L,N,R\}$.
 \begin{tabbing}
\qquad \=\+   
$\delta(q_0,a,\gamma)=(q_0,0\gamma,R)$, für $\gamma\in\Gamma$.\\
$\delta(q_0,\$,\gamma)=(q_1,\gamma,N)$, für $\gamma\in\Gamma$.\\
$\delta(q_1,x,1)=(q_1,\eps,L)$, für $x=0$ oder $x=\$$.\\
$\delta(q_1,x,0)=(q_0,1,N)$, für $x=0$ oder $x=\$$.\\
$\delta(q_1,x,Z_0)=(q_1,\eps,N)$, für $x=0$ oder $x=\$$.
 \end{tabbing}
Die übrigen Werte von $\delta$ (für $x=\%$) sind beliebig.
\begin{enumerate}
\item
Beschreiben Sie das Verhalten des Automaten
 bei Eingabe des Wortes $a^n$,
für $n=0,1,2,3$ und für allgemeines $n$.
\item
Bestimmen Sie die Entladefunktion $E\colon
Q\times \{0,\ldots,n+1\}\times \Gamma \to
Q\times \{0,\ldots,n+1\}$ bei Eingabe des Wortes $a^n$.
\end{enumerate}

\item
  \begin{enumerate}
  \item
Beschreiben Sie formal, wie man einen nichtdeterministischen
Zweiweg-Keller\-auto\-maten, der mit akzeptierenden Zuständen arbeitet,
in einen äquivalenten Zweiweg-Keller\-auto\-maten umwandelt, der mit leerem Keller
akzeptiert.
\item Beschreiben Sie die Transformation in die umgekehrte Richtung.
  \end{enumerate}

% \item
% Beweisen Sie, dass die kontextfreien Sprachen abgeschlossen
% gegenüber der Vereinigung mit regulären Sprachen sind.

\item Mit deterministischen Zweiweg-Kellerautomaten kann man alle
  deterministisch kontextfreien Sprachen akzeptieren.

\item (4 Zusatzpunkte)
Konstruieren Sie (a) eine Grammatik, (b)~einen Kellerautomaten für die Sprache
$\{\,ww^R\mid w\in \{0,1\}^*\,\}$.


\item 
Beweisen Sie: Wenn eine Sprache von einem deterministischen
Kellerautomaten (mit akzeptierenden Zuständen) akzeptiert wird,
dann gibt es eine eindeutige kontextfreie Sprache für diese Grammatik.


\item Sind die Sprachen, die von deterministischen
  Zweiweg-Kellerautomaten akzeptiert werden, abgeschlossen gegenüber
  Umkehrung (Spiegelbild)?


\end{enumerate}
\end{document}
