%  2. Klausur GTI WS 1999/2000
\documentclass [12pt] {article}
%\usepackage [reqno] {amsmath}
\usepackage{amsfonts}
\usepackage {german}
\usepackage[latin1]{inputenc}
\textwidth=16cm
\textheight=22,6cm
\hoffset = -17mm
\voffset = -20mm

\let\seite\relax
\let\eps\varepsilon

\begin{document}

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

 2.~Klausur,
Mittwoch, 11. Juli 2001
---
Lösungen

}
\end{centering}
\par\bigskip
\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.

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

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

\seite
\begin{enumerate}

\item (10 Punkte)
$L_1$ sei eine kontextfreie Sprache über dem Alphabet $\{0,1\}$, und
$$ L_2= \{\, w_10w_20\ldots w_n0\mid w_1w_2\ldots w_n\in L_1,\ n\ge0
\,\}$$
sei die
Sprache, wo nach jedem Buchstaben jedes Wortes eine Null eingefügt
ist.
Beweisen Sie, dass $L_2$ ebenfalls kontextfrei ist.

{\bf Lösung:}
$G_1$ sei eine Grammatik, die $L_1$ erzeugt.
Ersetze auf der rechten Seite aller Regeln 0 durch 00 und 1 durch 10.
Die entstehende Grammatik erzeugt $L_2$.

{\bf Alternativlösung:}
$K_1$ sei ein Kellerautomat, der $L_1$ akzeptiert.
Für jeden Übergang $(q,a,\gamma,q',\gamma')\in \delta_1$ mit
$a\in\Sigma$
erzeugen wir zwei Übergänge
$(q,a,\gamma,q_i,\gamma)$ und
$(q_i,0,\gamma,q',\gamma')$
in $\delta_2$,
wobei $q_i$ jedesmal ein neuer Zustand ist, der sonst nirgends vorkommt.
Die Übergänge $(q,\eps,\gamma,q',\gamma')\in \delta_1$ übernehmen wir
unverändert
in $\delta_2$.

Nach jedem Buchstaben des Eingabewortes muss somit eine 0 gelesen
werden,
dass der Automat weiterarbeiten kann.
Der neue Kellerautomat akzeptiert~$L_2$.

\seite


\item (10 Punkte)
Konstruieren Sie eine kontextfreie Grammatik für die
Sprache der Wörter über $\{0,1\}$, die \emph{kein} Palindrom sind:
$$L = \{\,w\mid w\ne w^R\,\}$$

{\bf Lösung:}\quad $
\begin{array}[t]{l}
S\to 0S0 \ \bigm| \ 1S1 \ \bigm| \ 0T1 \ \bigm| \ 1T0
\\[0,7\jot]
T\to 0T \ \bigm|\ 1T \ \bigm|\ \eps
\end{array}$

Jedes Wort $w\in L$ muss Länge $|w|\ge 2$ haben, ist also
von der Form $w=aw'b$ mit $a,b\in \{0,1\}$.
Wenn $a\ne b$, dann kann $w'\in \{0,1\}^*$ beliebig sein.
Die Sprache $ \{0,1\}^*$ wird vom Symbol $T$ erzeugt.
Wenn $a= b$ ist, dann darf $w'$ kein Palindrom sein.
Es ist also $w'\in L$ ($S\to w'$).

\seite
\item (10 Punkte)
Wandeln Sie die folgende Grammatik in Chomsky-Normalform um.
Prüfen Sie dann mit dem CYK-Algorithmus nach, dass das Wort
$a*a-a-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 S-A \ \bigm| \ A*A
\\
A\to A-A \ \bigm|\ a
\end{array}
$$
{\bf Lösung:}
Erster Schritt. Separation der Terminalsymbole von den Variablen.
$$
\begin{array}{l}
S\to SMA \ \bigm| \ APA,\qquad
A\to AMA \ \bigm|\ a, \qquad
M\to -, \qquad
P\to *
\end{array}
$$

Zweiter Schritt. Zu lange Regeln werden in
eine Kette von Regeln aufgespalten.
$$
\begin{array}{lll}
S\to SS_1, \quad &S_1\to MA\qquad \quad &
A\to AA_1, \quad A_1\to MA
\\
S\to AS_2, & S_2\to PA
 &A\to a, \qquad
M\to -, \qquad
P\to *
\end{array}
$$

Dritter Schritt:
Regeln der Form $A\to\eps$ werden eliminiert,
und es wird sichergestellt, dass $S$ nicht auf der rechten Seite einer Regel
vorkommt.
Da wir keine solchen Regeln haben, ist dieser Schritt nicht notwendig.
Wenn man trotzdem $S$ nicht auf der rechten Seite einer Regel haben
möchte,
kann man eine neue Startvariable $S_0$ einführen und dann die Regel
$S_0\to S$ eliminieren.
Das würde auf die folgende Grammatik führen:
$$
\begin{array}{lll}
S_0\to SS_1 \rlap{$\ \bigm|\ AS_2$}
\\
S\to SS_1, \quad &S_1\to MA\qquad \quad &
A\to AA_1, \quad A_1\to MA 
\\
S\to AS_2, \quad & S_2\to PA
&A\to a, \qquad
M\to -, \qquad
P\to *
\end{array}
$$



Vierter Schritt:
 Elimination der zu kurzen Regeln der Form $A\to B$.
Da keine solchen Regeln vorkommen,  entfällt dieser Schritt.

\medbreak
Ausführen des CYK-Algorithmus:

\def\baum#1#2#3{% #1=Wurzel #2=linker #3=rechter Teilbaum
\vtop{
\setbox0=#2 \setbox2=#3
\offinterlineskip
\halign{##\cr
\hss$\strut#1$\hss\cr
\hss \vrule height 4pt\hss\cr
\hskip 0,5\wd0
\hrulefill
\hskip 0,5\wd2\cr
\hskip 0,5\wd0
\vrule height 4pt
\hfill
\vrule height 4pt
\hskip 0,5\wd2\cr
\box0\quad \box2\cr
}}}

\def\blatt#1#2{\vtop{\offinterlineskip
\halign{\hss$##$\hss\cr
#1\strut\cr\vrule height 8pt\cr#2\strut\cr}}}

\noindent\quad
$
\openup 0,3\jot
\catcode`.=\active
\let.=\emptyset
\vbox{\halign{ &\strut\hbox to 6mm{\hss$#$\hss}\cr
   a&&*&&a&&-&&a&&-&&a\cr
\noalign{\hrule}
  A&&P&&A&&M&&A&&M&&A\cr
& .&&\underline{S_2}&&.&&S_1,A_1&&.&&S_1,\underline{A_1}\cr
&& \underline S&&.&&A&&.&&\underline A\cr
&&& .&&S_2&&.&&\underline{S_1},A_1\cr
&&& &S&&.&&A\cr
&&&&&.&&S_2\cr
&&&&&&\underline S\cr
}\vss}
$
\hfill
\vbox to 0pt{\vss
\baum S{\baum{S} {\blatt Aa}{\baum {S_2} {\blatt P*} {\blatt Aa}}}
{\baum{S_1} {\blatt M-}
{\baum A {\blatt Aa}{\baum {A_1} {\blatt M-} {\blatt Aa}}}}
\null}
\quad\null

Das Symbol $S$ erscheint im untersten Element.
Daher wird das Wort von der Grammatik erzeugt.
Es gibt mehrere Möglichkeiten, die Entstehung
des Startsymbols zurückzuverfolgen.
Wenn man zum Beispiel die Einträge auswählt, die in der Tabelle
unterstrichen sind, erhält man Ableitungsbaum auf der rechten Seite.
Er entspricht der folgenden Linksableitung. (Es gibt noch vier
andere Ableitungsbäume.)
\\
\null\quad $S
\to SS_1
\to AS_2S_1
\to aS_2S_1
\to aPAS_1
\to a{*}AS_1
\to a{*}aS_1
\to a{*}aMA\to{}\\{}\quad
\to a{*}a{-}A
\to a{*}a{-}AA_1
\to a{*}a{-}aA_1
\to a{*}a{-}aMA
\to a{*}a{-}a{-}A
\to a{*}a{-}a{-}a
$

\seite

\item (Zusatzfrage, 5 Punkte)
Ist das Komplement $\bar U$ der universellen Sprache,
$$\bar U = \{\, \langle M\rangle w \mid 
\hbox{$M$ akzeptiert $w$ \emph{nicht}}\,\}
$$
entscheidbar?
Beweisen Sie Ihre Antwort.

{\bf Lösung:}
Eine Sprache ist genau dann entscheidbar, wenn ihr Komplement
entscheidbar ist.
Da die universelle Sprache $U$ nicht entscheidbar ist, ist auch
$\bar U$ nicht entscheidbar.

\end{enumerate}

\end{document}

