% 11. Uebungsblatt GTI SS 2001
\documentclass [11pt] {article}
%\usepackage [reqno] {amsmath}
\usepackage{amsfonts}
\usepackage {german}
\usepackage[latin1]{inputenc}
\textwidth=16,1cm
\textheight=24cm
\hoffset = -19mm
\voffset = -25mm

\setcounter{page}{11}
\let\eps=\varepsilon
\begin{document}

\begin{centering}
{\large \bf Grundlagen der  theoretischen Informatik, SS 2001 ---
 11.~\"Ubungsblatt\par
}
\medskip
ergänzende Zusatzübungen zur Wiederholung und Vertiefung
\smallskip

freiwillige Abgabe bis Montag, 16. Juli 2001
\par \medskip
\end{centering}
\hrule
\medskip


\begin{enumerate}
\setcounter{enumi}{67}

\item %
  \begin{enumerate}
  \item  (3 Zusatzpunkte) 
Beschreiben Sie formal, wie man einen nichtdeterministischen
Kellerautomaten, der mit akzeptierenden Zuständen arbeitet,
in einen äquivalenten Kellerautomaten umwandelt, der mit leerem Keller
akzeptiert.
\item Beschreiben Sie die Transformation in die umgekehrte Richtung.
\item Lösen Sie die beiden obigen Aufgaben
auch für deterministische Zweiweg-Keller\-auto\-maten.
  \end{enumerate}

\item (6 Zusatzpunkte)
Beweisen Sie, dass die kontextfreien Sprachen abgeschlossen
gegenüber dem Durchschnitt mit regulären Sprachen sind.
(Hinweis: Wählen Sie ein geeignetes Maschinenmodell für die kontextfreien
Sprachen und verfahren Sie ähnlich wie bei Aufgabe~19.)

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

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

\item
Konstruieren Sie einen deterministischen Kellerautomaten für die Sprache
$$\left\{\,w\#w^R\bigm|w\in \{-1,1\}^*\,\right\}.$$

\item
Konstruieren Sie einen deterministischen Kellerautomaten für die
Sprache der Wörter, die gleich viele Nullen und Einsen enthalten.

\item Beweisen Sie, dass die Sprachen
$\{\,a^ib^ic^j \mid i,j\ge0\,\}$
und
$\{\,a^ib^jc^j \mid i,j\ge0\,\}$
deterministische kontextfreie Sprachen sind.
Zeigen Sie mit Hilfe dieser Sprachen, dass die
deterministischen kontextfreien Sprachen nicht gegenüber
dem Durchschnit abgeschlossen sind.

\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)?

\item (Schwierig, 5 Zusatzpunkte)
Sind die deterministischen kontextfreien Sprachen abgeschlossen
gegenüber Umkehrung?

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

\item
Welche Beispiele von Typ-0-Sprachen kennen Sie, die keine
Typ-1-Sprachen sind?
Welche Beispiele von Typ-1-Sprachen kennen Sie, die keine
Typ-2-Sprachen sind?
Welche Beispiele von Typ-2-Sprachen kennen Sie, die keine
Typ-3-Sprachen sind?

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

\end{enumerate}
\eject
\end{document}
