%  2b. Klausur GTI SS 2001
\documentclass [12pt] {article}
%\usepackage [reqno] {amsmath}
\usepackage{amsfonts}
\usepackage {german}
\usepackage[latin1]{inputenc}
\textwidth=16cm
\textheight=22cm
\hoffset = -17mm
\voffset = -20mm

\newif\iferstes
\erstestrue
\let\seite\relax
\let\eps\varepsilon

\begin{document}

\begin{centering}
{\large \bf Grundlagen der  theoretischen Informatik, SS 2001

\normalsize
Nachklausur zum 2.~Teil,
Dienstag, 9. Oktober 2001
---
Lösungen

}
\par \smallskip
\end{centering}$$
\begin{tabular}{|l| r r r r   |}
\hline
 
Aufgabe
\vrule height 12pt depth 6pt width 0pt
&\ 1 &\ 2 &\ 3 & (4) \ \\
\hline
Punkte
\vrule height 14pt depth 6pt width 0pt
& 10 & 10& 10 & (5) \ \\
\hline
Punkte
\vrule height 16pt depth 8pt width 0pt&&&&
\rlap{ \quad gesamt: }\\
\hline
\end{tabular}
$$       
\medskip
\hrule
\medskip

\noindent \emph{Anleitung}:
Bearbeiten Sie {jede} Aufgabe auf dem dafür vorgesehenen \emph{Blatt}.
Verwenden Sie gegebenfalls Ergänzungsblätter.
Schreiben Sie auf \emph{alle} Blätter Ihren Namen und Ihre
Matrikelnummer.


\noindent
Sie können alle Aussagen, die in der Vorlesung oder auf den
Übungsblättern vorgekommen sind, verwenden, ohne die Beweise
abzuschreiben.


\noindent
Kriterium für positive Bewertung: mindestens 50\,\%, das sind 15 Punkte.
\medskip
\hrule
\medskip

\seite
\begin{enumerate}

\item (10 Punkte)
Wandeln Sie die folgende Grammatik in Chomsky-Normalform um.
Prüfen Sie dann mit dem CYK-Algorithmus nach, dass das Wort
$aaa{+}aa{+}a{-}$  von dieser Grammatik
erzeugt wird, und geben Sie einen Syntaxbaum \emph{und} eine
Linksableitung (für die umgewandelte Grammatik) an.
$$
\begin{array}{l}
S\to SSS \ \bigm| \ A
\\
A\to A{+}A \ \bigm|\ AS{-} \ \bigm|\ a
\end{array}
$$
{\bf Lösung:}
Erster Schritt. Trennung von Variablen und Terminalsymbolen:
$$
S\to SSS \ \bigm| \ A,
\qquad
A\to APA \ \bigm|\ ASM \ \bigm|\ a,
\qquad
P\to {+},
\qquad
M\to {-}
$$
Zweiter Schritt. Elimination von zu langen Regeln:
$$
\begin{array}{l}
S\to ST, \ T\to SS; \quad S\to A
\\
A\to AB, \ B\to PA; \quad A\to AC, \ C\to SM
\\
P\to {+},
\ \
M\to {-},
\ \
A\to a
\end{array}
$$
Dritter Schritt. Elimination der zu kurzen Regel $S\to A$:
Sie wird ersetzt durch
$S\to AB$,
$S\to AC$,
$S\to a$.

Eine Linksableitung ist dann
$S\to
AC\to aC\to aSM
\to aSTM
\to aaTM
\to aaSSM
\to aaABSM
\to aaaBSM
\to aaaPASM
\to aaa{+}ASM
\to aaa{+}aSM
\to aaa{+}aaM
\to aaa{+}aa-$.
\seite


\item (10 Punkte)
Beweisen Sie, dass die folgenden Sprachen über dem
Alphabet
$\{a,b,c\}$
nicht
kontextfrei sind.
\begin{enumerate}
\item 
$L_1 = \{\,w %\in \{a,b,c\}^* 
\mid \hbox{$w$ enthält
gleich viele $a$'s, $b$'s und $c$'s.}\,\}$
\item 
$L_2 = \{\,a^ib^jc^k\mid 1\le i<j=k\,\}$
\end{enumerate}

{\bf Lösung zu (a):}
$L_1 \cap a^*b^*c^* = \{\,a^ib^ib^i\mid i\ge0\,\}$
und diese Sprache ist bekanntlich nicht kontextfrei.
Beim Schnitt mit einer regulären Sprache bleibt eine
kontextfreie Sprache kontextfrei.

Man kann auch das Pumping-Lemma auf $a^Nb^Nc^N \in L_1$ anwenden:
$a^Nb^Nc^N=uvxyz$.
Wegen $|vxy|\le N$ kann $vy$ nicht $a$'s, $b$'s und $c$'s, enthalten.
Daher ist $vy\in \{a,b\}^+ \cup \{b,c\}^+$.
Somit enthält $uxz$ nicht gleich viele $a$'s, $b$'s und $c$'s.
Widerspruch.

{\bf Lösung zu (b):}
Beweis durch Widerspruch.
$N$ sei die Konstante aus
  dem Pumping-Lemma.
Wende das Pumping-Lemma auf $a^Nb^{N+1}c^{N+1} \in L_2$ an:
 Dann ist $a^Nb^{N+1}c^{N+1} = uvxyz$
mit $|vxy|\le N$ und $|vy|\ge 1$,
 und alle Wörter
 $uv^ixy^iz$ für $i\ge0$ gehören zu~$L_2$.
 \begin{enumerate}
 \item 
Wenn $v$ oder $y$ nicht von der Form $a^*\cup b^* \cup c^*$ ist,
dann wäre $uv^2xy^2z\notin a^*b^*c^*$ und somit
 $uv^2xy^2z\notin L_2$.
 \item
Wenn $y=c^i$ ($i\ge 0$) ist, muss $v=b^i$ sein, denn sonst hätte
$uxz$ nicht gleich viele $b$'s und $c$'s. Also ist $i\ge 1$.
Dann hat aber $uxz$ nicht mehr $b$'s als $a$'s und
gehört somit nicht zu $L_2$, ein Widerspruch.
 \item
Wenn $y=b^i$ ($i\ge 1$) ist, dann ist $v\in a^*\cup b^*$,
und  $uv^2xy^2z$ enthält mehr $b$'s als $c$'s.
 \item
Wenn $y=a^i$ ($i\ge 1$) ist, dann ist auch $v\in a^*$,
und  $uv^ixy^iz$ enthält für genügend großes $i$ mehr $a$'s als $b$'s.
 \end{enumerate}
Damit sind alle Möglichkeiten für $y$ erschöpft.

\seite
\item (10 Punkte)
Geben Sie für die folgende Grammatik einen äquivalenten
Kellerautomaten an. (Entscheiden Sie selbst, wie der
Automat akzeptieren soll.)
$$
\begin{array}{l}
S\to S-A \ \bigm| \ A*A
\\
A\to A-A \ \bigm|\ a
\end{array}
$$

{\bf Lösung:}
"`Mechanische"' Übersetzung der Grammatik.
$Q=\{q_0\}$, $\Gamma=\{S,A,{*},{-},a\}$,
$\Sigma = \{a,{*},{-}\}$, $Z_0=S$.
Es gibt nur einen einzigen Zustand $q_0$; deshalb werden im Folgenden bei
$\delta \subseteq Q\times \Gamma \times \Sigma \times Q\times
\Gamma^*$ die Zustände
nicht geschrieben.
$$\delta = \{
(S,\eps,A-S),
(S,\eps,A*A),
(A,\eps,A-A),
({-},{-},\eps),
({*},{*},\eps),
(A,{a},\eps)
\}.$$
(Achtung auf die Reihenfolge bei der ersten Regel.)
Der Automat akzeptiert mit leerem Keller.

Man kann auch zur größeren Klarheit
eigene Kellersymbole für $*$ und $-$ einführen, dann ist
$$\delta = \{
(S,\eps,AMS),
(S,\eps,ATA),
(A,\eps,AMA),
(M,{-},\eps),
(T,{*},\eps),
(A,{a},\eps)
\}.$$

Andere (ursprünglich nicht vorgesehene) Lösungsmöglichkeit:
Die Grammatik erzeugt die reguläre Sprache $L = a(-a)^*{*}a(-a)^*$.
Der Kellerautomat kann einen endlichen Automaten für diese Sprache
simulieren.


\seite

\item (Zusatzfrage, 5 Punkte)
Ist die Sprache
$$L = \{\,0^i1^j0^k1^l \mid i+l=j+k \,\}$$
kontextfrei?
Ist sie regulär?
Beweisen Sie Ihre Antworten.

{\bf Lösung:}
1. Sie ist kontextfrei.
Man kann $L=L_1\cup L_2$ schreiben mit
$$ L_1 = \{\,0^i1^j0^k1^l \mid i+l=j+k, i\le j \,\},\quad
%und
 L_2 = \{\,0^i1^j0^k1^l \mid i+l=j+k, l\le k \,\}$$
$L_1$ kann man mit $m=i-j$ so schreiben:
$$ L_1 = \{\,0^i1^i 1^m0^k1^l \mid i\ge 0, m+k=l \,\}
 = \{\,0^i1^i \mid i\ge 0 \,\} \cdot
 \{\, 1^m0^k1^{m+k} \mid m,k\ge 0 \,\},
$$
und analog für $L_2$.
Diese Sprachen lassen sich einfach durch kontextfreie Grammatiken
erzeugen. Die folgende Grammatik erzeugt $L$.
$$
\begin{array}{ll}
S\to NA \ \bigm| \ AN \quad
\\
N\to 0N1 \bigm|\ \eps \quad& \hbox{($N$ erzeugt $\{\,0^i1^i\,\}$.)}
\\
A\to 1A1 \bigm|\ N& \hbox{($A$ erzeugt $\{\,1^i0^j1^{i+j}\,\}$.)}
\\
B\to 0B0 \bigm|\ N& \hbox{($B$ erzeugt $\{\,0^{i+j}1^i0^j\,\}$.)}
\end{array}
$$


Ein anderer Beweis konstruiert einen (nichtdeterministischen)
Kellerautomaten, der die Differenz zwischen den Häufigkeiten
der Symbole zählt.
Der Automat durchläuft 4 Phasen:
\smallskip
\\\null\qquad Phase 1 (Zustand $q_0$): Jede 0 wird als $+1$ gezählt.
\\\null\qquad Phase 2 (Zustand $q_1$): Jede 1 wird als $-1$ gezählt.
\\\null\qquad Phase 3 (Zustand $q_2$): Jede 0 wird als $-1$ gezählt.
\\\null\qquad Phase 4 (Zustand $q_3$): Jede 1 wird als $+1$ gezählt.
\smallskip
\\
Der Automat akzeptiert, wenn der Zähler am Ende 0 ist.
%% ....
Ein Zähler kann durch eine Folge von $+$-Symbolen (für positive Werte)
oder $-$-Symbolen (für negative Werte) auf dem Keller dargestellt
werden. Ein "`leerer"' Keller entspricht dem Wert~0.
Der Übergang von einer Phase zur nächsten ist nichtdeterministisch,
weil $j=0$ oder $k=0$ nicht ausgeschlossen ist.

Der folgende Automat akzeptiert $L$ durch leeren Keller:
$Q=\{q_0,q_1,q_2,q_3\}$,
$\Gamma=\{Z_0,+,-\}$,
und
\begin{eqnarray*}
&\delta = \{&
(q_0,\gamma,0,q_0,{+}\gamma),
(q_0,\gamma,\eps,q_1,\gamma),
\\&&
(q_1,+,1,q_1,\eps),
(q_1,\gamma^-,1,q_1,{-}\gamma^-),\,
(q_1,\gamma,\eps,q_2,\gamma),
\\&&
(q_2,+,0,q_2,\eps),
(q_2,\gamma^-,0,q_2,{-}\gamma^-),
(q_2,\gamma,\eps,q_3,\gamma),
\\&&
(q_3,{-},1,q_3,\eps);
\
(q_3,Z_0,\eps,q_3,\eps)
\ \
\},
\end{eqnarray*}
für 
$\gamma\in\Gamma$
% $\gamma^+\in\{Z_0,{+}\}$,
und $\gamma^-\in\{Z_0,{-}\}$.

2. Die Sprache $L$ ist nicht regulär.
Zum Beispiel ist $L\cap 010^+1^+ = \{\,010^i1^i\mid i\ge 1\,\}$,
und diese Sprache ist nicht regulär, ahnlich wie die bekannte
nichtreguläre Sprache $\{\,0^i1^i\mid i\ge 1\,\}$.
(Vergleiche auch Aufgabe 4 der ersten Nachklausur zum ersten Teil.)

Man kann auch das Pumping-Lemma direkt anwenden.
\end{enumerate}


\end{document}

