\documentclass[12pt]{article}
\usepackage{german}
\usepackage[latin1]{inputenc}
\usepackage{amsfonts}
\textwidth=16,1cm
\textheight=24cm
\hoffset = -19mm
\voffset = -25mm
\let\eps\varepsilon
\begin{document}
{\bf Musterl\"osungen zu Grundlagen der theoretischen Informatik (skizziert)}
\begin{itemize}
\item[(3a)] $L_2=(a+\varepsilon)(ba)^*(b+\epsilon)$
oder $L_2=\varepsilon + L_{2}^{'}$ mit $L_{2}^{'}=a(ba)^*(b+\varepsilon)+b(ab)^*(a+\varepsilon)$
oder $L_{2}^{'}=a+(a+\varepsilon)(ba)^*b(a+\varepsilon)$\\
$L_3=\varepsilon +L_{3}^{'}$ mit $L_{3}^{'}=L_{2}^{'}+L_2(cL_{2}^{'})^*cL_2$\\
$L_4=\varepsilon+L_{3}^{'}+L_3(dL_{3}^{'})^*dL_3$

\item[(3b)] $(aa^++bb^++cc^+)^*$

\item[(3c)] $l_n=l_{n-1}+(|\Sigma|-1)l_{n-2}.$
(W\"orter mit mindestens drei gleichen Buchstaben am Ende, plus W\"orter, deren letzter Block genau die L\"ange 2 hat).
$l_1=0,l_2=|\Sigma|$.
F\"ur $\Sigma_2$ ergeben sich die doppelten Fibonacci-Zahlen. F\"ur $\Sigma_3$ erh\"alt man $l_n=(2^{n+1}-2(-1)^n)/3$. Allgemein ist
$$l_n=\left[\textstyle \left(\frac{1}{2}+\sqrt{|\Sigma|-\frac{3}{4}}\right)^n
-\left(\textstyle\frac{1}{2}-\sqrt{|\Sigma|-\frac{3}{4}}\right)^n\right]
\biggm/ \sqrt{\textstyle |\Sigma|-\frac{3}{4}}.$$

\item[(8b)] keine Kongruenzrelation f\"ur $|\Sigma|\ge2$: $a=d=\varepsilon$ und $b,c\in\Sigma$, $b\not=c$.

\item[(8c)]Es ist eine Kongruenzrelation. Die Eigenschaften einer \"Aquivalenzrelation weist man leicht nach.\\
 Wenn $a=b=\varepsilon$, ist $ac=c$ und $bd=d$, und die Aussage ist trivial. Wenn $a\not=\varepsilon\not=b$ ist, dann hat $ac$ den selben Anfangsbuchstaben wie $a$ und $bd$ wie $d$.

\item[(8d)] keine Kongruenzrelation: $a=d=0$, $b=c=1$.

\item[(10a)] $F=\{q_6\}$, \
\begin{tabular}[t]{c|ccccccc}
$\delta$ & $q_0$ & $q_1$ & $q_2$ & $q_3$ & $q_4$ & $q_5$ & $q_6$ \\ \hline
$0$ & $q_1$ & $q_1$ & $q_3$ & $q_1$ & $q_5$ & $q_1$ & $q_6$\\
$1$ & $q_0$ & $q_2$ & $q_0$ & $q_4$ & $q_0$ & $q_6$ & $q_6$
\end{tabular}

\item[(10b)] der gleiche Automat wie (10a), mit $F'=Q-F$.

\item[(10f)] Die W\"orter $\varepsilon,0,01,010,0101,01010,010101$ sind in verschiedenen Klassen $L_q(M)$, weil die Relation in der letzten Zeile von Aufgabe 9 nicht erf\"ullt ist.\\
Zum Beispiel f\"ur $w_1=010$ und $w_2=01010$ gilt: f\"ur $x=11$: $w_1x\not\in L$, aber $w_2x \in L$.\\
Im Allgemeinen kann man $x$ so w\"ahlen, dass $wx=0101011$ ist, wobei $w$ das k\"urzere der Worte $w_1$ und $w_2$ ist. Daher hat $M$ mindestens 7 Zust\"ande. Dieses zeigt auch, dass der Automat aus Aufgabe 10a der Minimalautomat ist.

\item[(14)] Man beginnt mit
$$L_{ij}^{(0)}=\{a\in \Sigma|(i,a,j)\in \delta\} \quad (\cup\{\varepsilon\}
\hbox{, falls $i=j$ ist}).$$
Am Ende muss man $L(M)$ als Vereinigung
der $L_{q_0,f}^n$
auch über alle
Startzustände $q_0\in Q_0$ bilden. 

\item[(15)] NEA's: Erzeuge einen neuen (einzigen) Endzustand $f$.
F\"ur alle \"Uberg\"ange, die zu einem bisherigen akzeptierenden Zustand gef\"uhrt haben, f\"uge einen entsprechenden \"Ubergang zu $f$ hinzu.
Formal:
$$\delta':=\delta \cup \{\,(q,a,f)\mid (q,a,r)\in \delta \mbox{ f\"ur ein } r\in F\,\}.$$
Falls $\varepsilon \in L (M)$ ist, wird $f$ \"uberdies zu einem Anfangszustand erkl\"art.

(Man kann auch erreichen, dass es nur einen einzigen Anfangszustand {\bf und} nur einen einzigen Endzustand gibt.)

DEA's: Solche Automaten erkennen nicht alle Sprachen. Beispiel:
$0^*+1^*$.
Mit Aufgabe 9 kann man zeigen, dass $\delta(q_0,0)\not= \delta (q_0,1)$ sein muss. Beides sind jedoch akzeptierende Zust\"ande.

\item[(16)] Zu jedem NEA gibt es einen \"aquivalenten DEA. Dieser ist ein NEA mit einem einzigen Anfangszustand.
Die Zusatzfrage geht \"ahnlich wie Aufgabe 15.

\item[(17a)] DEA und NEA benötigen beide mindestens 5 Zustände.
Nichtdeterminismus bringt keine Ersparnis.

\item[(17b)] Der NEA kommt mit $5=n+1$ Zuständen aus (Umkehrung von 17a).
Ein DEA braucht mindestens $16=2^n$ Zustände. Im allgemeinen ist
der Unterschied zwischen NEA und DEA in diesem Beispiel exponentiell.

\item[(19)] $Q=Q_1\times Q_2$, $q=(q_1{}_0,q_2{}_0)$, $F=F_1\times F_2$, 
$\delta ((q_1,q_2),a) = (\delta_1 (q_1,a),\delta_2(q_2,a))$

\item[(26a)] Wende das Pumping-Lemma auf $w=0^n10^n$ an.
$L_1$ ist nicht regulär.

\item[(26b)] Wende das Pumping-Lemma auf $w=0^{n^2}$ an.
$n^2+k$ ist für kein $k$ mit $1\le k \le n$ eine
Quadratzahl, und somit ist $0^{n^2+k}\notin L_2$.
$L_2$ ist nicht regulär.

\item[(26c--e)] $L_5 \cap \{00,01,10,11\}^* \cap 0^*1^n$
ist die Sprache $\{\,0^n1^n\,\}$, die bekanntlich nicht
regulär ist. Da die regulären Sprachen abgeschlossen unter
$\cap$ sind, ist auch $L_5$ nicht regulär.
Dasselbe Argument zeigt, dass $L_4$ nicht regulär ist.
$L_3$ ist ebenfalls nicht regulär.

\item[(26f)] $L_6 =\{01,10\}^*\cdot \{\eps,0,1\}$ ist regulär.

\item[(28)] $h_3(L_4) =(01)^*$ und $h_2(L_1)=1^*$ sind regulär.
$h_1(L)$ ist genau dann regulär, wenn $L$ regulär ist.

\item [(30)]
Beginnend von rechts, wird jeweils das erste nicht markierte
Bit von $y$ und von $x$ markiert. Wenn dieses Bit von $y$ gleich 1 ist,
wird es zur entsprechenden Stelle von $x$ addiert, und gegebenenfalls
ein Übertrag nach links weitergereicht.
Ein $B$-Symbol am Anfang von
$x$ wird dabei wie eine $0$ behandelt.
Wenn alle Stellen von $y$ markiert sind, werden alle Markierungen
gelöscht, und der Automat hält.
\par\smallskip

  {\offinterlineskip \small
\halign{\hfil$#$\hfil\ \strut\vrule\ &
 \hfil$#$\hfil\ & \hfil$#$\hfil\ &
 \hfil$#$\hfil\ & \hfil$#$\hfil\ &
 \hfil$#$\hfil\ & \hfil$#$\hfil\hskip-0,3em &
\hskip-0,3em \hfil$#$\hfil\ &\vrule\  #\hfil\cr
\delta&0&1&\bar0&\bar1&\#&\$&B&Kommentar\cr
\noalign{\hrule}
q_0& (q_0,0,R) & (q_0,1,R) &(q_0,\bar0,R)&(q_0,\bar1,R)&
 (q_0,\#,R) & (q_1,\$,L) &-
&fahre nach rechts\cr
q_1& (q_2,\bar0,L) & (q_4,\bar1,L) &(q_1,\bar0,L)&(q_1,\bar1,L)& (q_7,\#,R) &
  - & -
&finde erstes nicht markiertes\cr
&&&&&&&& \ \ Bit $y_0$ von $y$ und markiere es\cr
q_2& (q_2,0,L) & (q_2,1,L) &-&-& (q_3,\#,L) &
  - & -
&falls $y_0=0$, finde erstes unmar-\cr
q_3& (q_0,\bar0,R) & (q_0,\bar1,R) &(q_3,\bar0,L)&(q_3,\bar1,L)& - &
  - & (q_0,\bar0,R)
&\ \ kiertes Bit von $x$, markiere es.\cr
q_4& (q_4,0,L) & (q_4,1,L) &-&-& (q_5,\#,L) &
  - & -
&falls $y_0=1$, finde erstes Bit\cr
q_5& (q_0,\bar1,R) & (q_6,\bar0,L) &(q_5,\bar0,L)&(q_5,\bar1,L)& - &
  - & (q_0,\bar1,R)
&\ \ von $x$,
markiere es, addiere 1,\cr
q_6& (q_0,1,R) & (q_6,0,L) &-&-&-&
  - & (q_0,1,R)
&gegebenenfalls Übertrag\cr
q_7& -&-&(q_7,\bar0,R) & (q_7,\bar1,R) &-&
 (q_8,\$,L)&-
&Ende, fahre ganz nach rechts\cr
q_8& (q_8,0,L)&(q_8,1,L)&(q_8,0,L) & (q_8,1,L) &(q_8,\#,L)&-& (q_F,B,R)
& nach links, lösche Markierungen\cr
}}
$ \let\oldvdash=\vdash \def\vdash{
            \mskip 1,8mu plus2mu
\allowbreak\oldvdash\allowbreak  \mskip 0,0mu plus2mu
}
 \def \q_#1{{\mathit {q_{\mathrm#1}}}}
\catcode`q=\active
\let q=\q
\tt
 q_0 101\#11\$
\vdash
 1q_0 01\#11\$
\vdash
 10q_0 1\#11\$
\vdash
 101q_0 \#11\$
\vdash
 101\#q_0 11\$
\vdash
 101\#1q_0 1\$
\vdash
 101\#11q_0 \$
\vdash
 101\#1q_1 1\$
\vdash
 101\#q_4 1\bar 1\$
\vdash
 101q_4 \#1\bar 1\$
\vdash
 10q_5 1\#1\bar 1\$
\vdash
 1q_6 0\bar0\#1\bar 1\$
\vdash
 11q_0 \bar0\#1\bar 1\$
\vdash
 11 \bar0q_0\#1\bar 1\$
\vdash
 11 \bar0\#q_01\bar 1\$
\vdash
 11 \bar0\#1q_0\bar 1\$
%\stackrel*\vdash
% 10\bar0 \bar0\#q_0\bar 1\bar 1\$
\vdash \cdots \vdash
% 10\bar0 \bar0\#\bar 1q_0\bar 1\$
%\vdash
 10\bar0 \bar0\#\bar 1\bar 1q_0\$
\vdash
 10\bar0 \bar0\#\bar 1q_1\bar 1\$
\vdash
 10\bar0 \bar0\#q_1\bar 1\bar 1\$
\vdash
 10\bar0 \bar0q_1\#\bar 1\bar 1\$
\vdash
 10\bar0 \bar0\#q_7\bar 1\bar 1\$
\vdash
 10\bar0 \bar0\#\bar 1q_7\bar 1\$
\vdash
 10\bar0 \bar0\#\bar 1\bar 1q_7\$
\vdash
 10\bar0 \bar0\#\bar 1q_8\bar 1\$
\vdash
 10\bar0 \bar0\#q_8\bar11\$
\vdash
 10\bar0 \bar0q_8\#11\$
\vdash
 10\bar0q_8\bar0\#11\$
\vdash
 10q_8\bar00\#11\$
\vdash
 1q_8000\#11\$
\vdash
 q_81000\#11\$
\vdash
 q_8B1000\#11\$
\vdash
 q_F1000\#11\$
.$
\item [(33)]
\begin{tabbing}
Fall 1. $y=\eps$:\\
  \qquad\=Fall 1L. $\delta(q,B)=(q',a,L)$.\\
\>  \qquad\=Fall 1L$\eps$. $x=\eps$: Dann ist $x'=\eps$ und $y'=Ba$.\\
\>\>   Fall 1L$+$. $x=ux_0$ mit $x_0\in\Gamma, u\in\Gamma^*$:
          Dann ist $x'=u$ und $y'=x_0a$.\\
\>  Fall 1N. $\delta(q,B)=(q',a,N)$: Dann ist $x'=x$ und $y'=a$.\\
\>  Fall 1R. $\delta(q,B)=(q',a,R)$: Dann ist $x'=xa$ und $y'=\eps$.\\

Fall 2. $y=y_1z$ mit $y_1\in\Gamma, z\in\Gamma^*$:\\
\>  Fall 2L. $\delta(q,y_1)=(q',a,L)$:\\
\>\>   Fall 2L$\eps$. $x=\eps$: Dann ist $x'=\eps$ und $y'=Baz$.\\
\>\>   Fall 2L$+$. $x=ux_0$ mit $x_0\in\Gamma, u\in\Gamma^*$:
          Dann ist $x'=u$ und $y'=x_0az$.\\
\>  Fall 2N. $\delta(q,y_1)=(q',a,N)$: Dann ist $x'=x$ und $y'=az$.\\
\>  Fall 2R. $\delta(q,y_1)=(q',a,R)$: Dann ist $x'=xa$ und $y'=z$.
\end{tabbing}
In allen Fällen kann man noch, wenn man will, $x'=B$ oder $y'=B$ durch
$x'=\eps$ beziehungsweise $y'=\eps$ ersetzen.


\item [(35a)] Wahr. Man muss nur beim Entscheidungsalgorithmus
die Antworten JA und NEIN vertauschen.

Bei einem Beweis auf der Ebene von Turingmaschinen muss man
zunächst sicherstellen, dass die Maschine nur dann in einen
akzeptierenden Zustand geht, wenn sie anhält.
Man kann eine Turingmaschine, die immer hält, so modifizieren,
dass es nur zwei Haltezustände gibt, einen
akzeptierenden und
einen nicht akzeptierenden.
Durch Vertauschen dieser beiden Zustände erhält man eine
Turingmaschine für die komplementäre Sprache.

\item [(35b)] Wahr. Überprüfe zuerst, ob $w\in L_1$ ist.
Wenn ja, akzeptiere das Wort~$w$.
Wenn nein, überprüfe, ob $w\in L_2$ ist, und akzeptiere $w$
genau dann wenn $w\in L_2$ ist.

\item [(35c)] Wahr. Die Aussage ist logisch äquivalent zu~(35a).
\item [(35d)] Falsch. Wenn $D$ eine beliebige unentscheidbare
Sprache ist, dann ist auch ihr Komplement $\bar D$ unentscheidbar.
$D\cup \bar D = \Sigma^*$ ist jedoch trivialerweise entscheidbar.

\item [(36a)] 
Entscheidungsalgorithmus für das Eingabewort
  $w=w_1\ldots w_n$:
Für alle $i=0,\ldots,n$, teste ob
 $w_1\ldots w_{i-1}\in L_1$
und $w_i\ldots w_{n}\in L_2$ ist. Wenn ja, akzeptiere~$w$.
Wenn die Schleife beendet wird, verwirf~$w$.

\item [(36b)] 
$M_1$ und $M_2$ seien zwei Maschinen
mit $L(M_1)=L_1$ und $L(M_2)= L_2$,
Für das Eingabewort
  $w=w_1\ldots w_n$ gehen wir der Reihe nach
alle Tripel $(k_1,k_2,i)$ mit $k_1,k_2\ge0$, $0\le i\le n$ durch
(in irgendeiner passenden Reihenfolge),
und testen durch Simulation ob
$M_1$ das Wort
 $w_1\ldots w_{i-1}$ in $k_1$ Schritten akzeptiert und ob
$M_2$ das Wort
 $w_i\ldots w_{n}\in L_2$ in $k_2$ Schritten akzeptiert.
Wenn ja, akzeptieren wir~$w$.


\item [(37)] Die Vorwärtsrichtung ergibt sich aus (35a).
Wenn sowohl $L$ als
auch $\bar L$ rekursiv aufzählbar ist, gibt es Maschinen $M$ und $M'$
mit $L(M)=L$ und $L(M')=\bar M$.
Lass die Maschinen $M$ und $M'$ "`parallel"' laufen; das heißt,
simuliere abwechselnd einen Schritt von $M$ und einen Schritt
von~$M'$.
Mindestens eine der beiden Maschinen muss halten, und dann hat
man entschieden, ob das Wort zur Sprache $L$ gehört.

\item [(39)]
Wenn $M_0$ eine beliebige Turingmaschine ist,
dann gilt nach
Definition, mit $M=M_0$ und $w=\langle M_0\rangle$:
$$\langle M_0\rangle
\langle M_0\rangle \in U' \iff
\hbox{$M_0$ akzeptiert das
Wort $\langle M_0\rangle\langle M_0\rangle $ nicht}$$
Daher ist $L(M_0)\ne U'$, weil sich die beiden Sprachen
zumindest im Wort $\langle M_0\rangle\langle M_0\rangle $ unterscheiden.
Es gibt also keine Turingmaschine, die $U'$ akzeptiert,
und $U'$ ist nicht einmal rekursiv aufzählbar.

\item [(40a)]
$L_1$ is rekursiv.
Es genügt, die ersten $k$ Schritte der Maschine $M$ zu simulieren, um
die Zugehörigkeit zur Sprache $L_1$ zu entscheiden.

\item [(40b--c)]
$L_2$ ist rekursiv, mit dem gleichen Algorithmus wie für Aufgabe 40a.
%
%\item [(40c)]
Die rekursiven Sprachen sind abgeschlossen gegenüber Vereinigung und
Komplement, daher ist auch $L_3$ is rekursiv.

\item [(40d)]
$L_4$ is rekursiv aufzählbar, aber nicht rekursiv.
Eine Turingmaschine für $L_4$ braucht nur die Maschine $M$ zu
simulieren,
und die Eingabe zu akzeptieren, wenn $M$ mindestens $k$ Schritte
läuft und irgendwann danach in einem akzeptierenden Zustand hält.

Wenn $L_4$ rekursiv wäre, dann wäre auch die Sprache $(L_4\cup
L_1)\cap 1\{0,1\}^*$ (das sind die Eingaben mit $k=0$) rekursiv;
dies ist aber die universelle Sprache $U$.

\item [(41)]
Wenn $L$ endlich ist, ist es trivialerweise entscheidbar.
Wenn $L$ unendlich ist, muss $L=0^*$ sein,
denn mit $0^i$ gehören auch alle $0^j$ mit $j<i$ zu~$L$.
Auch diese Sprache ist klarerweise entscheidbar.

\item [(44b)] Wenn die Sprache $L$ rekursiv ist, dann kann
eine Maschine $M$ alle Wörter von $\Sigma^*$ in der
passenden Reihenfolge untersuchen, und diejenigen, die
zu $L$ gehören, auf das Ausgabeband schreiben.

Nehmen wir umgekehrt an, dass es eine solche Maschine $M$ gibt.
Falls die Sprache $L$ endlich ist, ist sie sowieso rekursiv.
Falls die Sprache $L$ unendlich ist, dann brauchen wir zur
Entscheidung, ob ein Wort $w\in L$ ist, nur zu warten, bis die
Maschine $M$ ein Wort schreibt, das länger als $w$ ist.
Wenn das Wort $w$ bis dahin noch nicht auf das Band geschrieben wurde,
dann gehört es nicht zu~$L$.

\item [(46)] Zwischen den Randmarkierungen $A$ und $B$ fährt das
"`Schiffchen"' $C/D$ beliebig oft
% zwischen dem rechten und dem linken Rand
hin und her. Beim Weg nach rechts verdoppelt das $C$ alle $a$'s,
die es trifft. Am rechten Rand wird das $C$ in $D$ umgewandelt,
und es fährt an den linken Rand, wobei es die $a$'s unverändert
überspringt. Am linken Rand wird $D$ wieder in $C$ umgewandelt, und er
ganze Prozess kann von vorne beginnen. In jedem Durchlauf wird die
Gesamtanzahl der $a$'s verdoppelt.
Am rechten Rand kann das $C$ auch mit dem $B$ zu $E$ verschmelzen.
Das $E$ wandert dann nach links und löst sich zusammen mit dem $A$
auf.
Damit ist der Ableitungsprozess beendet.

Die erzeugte Sprache ist $\{\,a^{2^i}\mid i\ge1\,\}$.

\item [(48)]
$\def\|{\ \bigm|\ }
\catcode`|=\active
\let |=\|
\begin{array}[t]{ll}
S\to S + B |S - B |B \qquad  &F \to V \uparrow F | V\\
% A_1\to A_1 + B |A_1 - B |B  &U_1 \to V \uparrow U_1 | V\\
B\to B * F |B \div F |F &V \to (S) | Z
%\\
% F_1 \to F_1 * G |F_1 \div G |G
\end{array}
$


\item [(54a)] $L_1$ ist nicht kontextfrei.
Beweis durch Widerspruch:
$N$ sei die Konstante aus
  dem Pumping-Lemma. Dann ist $0^N1^{N^2} = uvxyz$ und alle Wörter
$uv^ixy^iz$ gehören zu~$L_1$.
Die Möglichkeiten 
$vxy\in 0^+$
und
$vxy\in 1^+$ führen direkt zu einem Widerspruch, ebenso
$v \in 0^+1^+$,
$y \in 0^+1^+$, oder $y=\eps$.
Es ist also $v\in 0^*$ und $y=1^k$ für $1\le k\le N$
Somit ist $uv^2xy^2z \in 0^*1^{N^2+k}$. 
Jedoch ist $N^2+k$ keine Quadratzahl.
Die nächstgrößere Quadratzahl nach $N^2$ ist
$(N+1)^2=N^2+2N+1>N+k$


\item [(54b)] $S\to 0S \bigm| 0S1 \bigm| \eps \ $ erzeugt $L_2$.

\item [(54c)] $L_3$ ist nicht kontextfrei.
Beweis durch Widerspruch
mit  dem Pumping-Lemma.
$N$~sei die Konstante aus
  dem Pumping-Lemma. Dann ist $w=10^N10^N10^N10^N = uvxyz$ und alle Wörter
$uv^ixy^iz$ gehören zu~$L_3$.
Wegen
$|vxy|\le N$ kann $vxy$ höchstens eine~1 enthalten.
Wenn $vy$ eine Eins enthält, dann enthält $uxz\in L_3$ genau
drei Einsen, ein Widerspruch.
Es folgt, dass $vy\in 0^+$ ist. Somit ist jedes Wort
$uv^ixy^iz$ von der Form
 $0^j10^k10^l10^m$. Ein solches Wort ist nur dann ein
Doppelwort, wenn $j=l$ und $k=m$ ist.
$vxy$ kann nur Nullen aus einem oder aus zwei aufeinanderfolgenden
Nullerblöcken enthalten. Das heißt, die Wörter
$uv^ixy^iz=0^j10^k10^l10^m$ haben zwei oder drei Nullblöcke konstanter
Länge und ein oder zwei benachbarte Nullblöcke variabler Länge.
Unter diesen Einschränkungen kann aber die Bedingung
$j=l$ und $k=m$ nicht aufrechterhalten werden.

\item[(54d)]
$L_4$: $\begin{array}[t]{lll}
S\to 0S1 \bigm| T_1\bigm|U_1, \quad&
T_1\to 0T_1 0\bigm|T_2, \quad&
T_2\to 1T_2 0\bigm|\eps, \\ &
U_1\to 1U_1 1\bigm|U_2, &
U_2\to 0U_2 1\bigm|\eps.
\end{array}
$

$L_5$: $S\to 0S1 \bigm| S_{10}S_{01}\bigm|S_{01}S_{10}$, \
$S_{01}\to 0S_{01} 1\bigm|\eps$, \
$S_{10}\to 1S_{10} 0\bigm|\eps$.
(Mit Aufgabe~69 könnte man auch aus $L_5 = \{\,$gleich viele Nullen und
Einsen$\,\}\cap
 0^*1^*0^*1^*$ folgern, dass $L_5$ kontextfrei ist.)

\item [(54e)]
$S$: $\#(0) = 2\cdot \#(1)$. \quad
$S_+$: $\#(0) = 2\cdot\#(1)+1$. \quad
$S_-$: $\#(0) = 2\cdot\#(1)-1$.

$
S\to 1S_+S_+ \bigm| 0S_-\bigm|\eps \ , \quad
S_+\to 1S_+S_+S_+\bigm| 0S\ , \quad
S_-\to 1S_+ \bigm| 0S_-S_-
$.

\item [(55)] Dass jedes Wort der erzeugten Sprache
diese Eigenschaft hat, beweist man
leicht mit vollständiger Induktion nach der Länge der Ableitung.

Wir beweisen nun mit Induktion nach der Länge $n$, dass jedes
Wort $w$ der Länge~$n$ mit der angegebenen Eigenschaft von der
Grammatik erzeugt wird. Der Induktionsanfang $n=0$ ist offensichtlich
erfüllt.
Falls in $w$ jeder nichtleere Präfix $x$
\emph{mehr} $a$'s als $b$'s enthält, dann ist $w=aw'$, und
$w'$ hat die angegebene Eigenschaft. Also wird $w$ nach
Induktion durch die Ableitung $S\to aS \stackrel*\to aw'$
erzeugt.

Im anderen Fall sei $w_1$ der kürzeste nichtleere Präfix
von~$w$, in dem die $a$'s und $b$'s ausgeglichen sind. Dann
ist $w=w_1w_2$ und $w_1=aw_1'b$.
Man überlegt sich leicht, dass $w_1'$ und $w_2$ zur Sprache gehören,
und somit kann $w$ abgeleitet werden,
indem man mit der zweiten Regel anfängt:
$S\to aSbS \stackrel*\to aw_1'bS \stackrel*\to aw_1'bw_2$.

\item [(56)] Die Grammatik
$$
\begin{array}{l}
S\to T\ \bigm|\ U\\
T\to \textbf{if } (B)\ T \textbf{ else } T
\ \bigm| \  \textrm{print}(0); 
\ \bigm| \  \textrm{print}(1);
\ \bigm| \  \textrm{print}(2); \\
U\to \textbf{if } (B)\ S
\ \bigm|\
\textbf{if } (B)\ T \textbf{ else } U
\\
B \to \textrm{true}\ \bigm| \  \textrm{false}
\end{array}
$$
ist eine äquivalente eindeutige Grammatik.
Aus $T$ sind alle Ausdrücke ableitbar, bei denen kein
\textbf{else} mehr ``fehlt''.%
\footnote{siehe auch \texttt{http://www.inf.fu-berlin.de/%
\char`\~rote/Lere/Grundlagen\%20der\%20theoretischen\%20\allowbreak Informatik/bison/%
Bedingungen.y}}
Durch geeignete Klammerung kann man übrigens erreichen, dass das
angegebene Programm auch 0 oder 1 druckt.%
\footnote{siehe auch \texttt{http://www.inf.fu-berlin.de/%
\char`\~rote/Lere/Grundlagen\%20der\%20theoretischen\%20\allowbreak Informatik/bison/%
test-Aufgabe56}}

\item [(58)] 
In einer Grammatik in CNF mit $n$ Variablen, die eine endliche
Sprache erzeugt, ist das längste Wort höchstens $2^{n-1}$ Zeichen lang.
Der Beweis geht durch vollständige Induktion. Der Fall $n=1$ ist einfach.
Wir können annehmen, dass die Grammatik keine
  überflüssigen Variablen enthält.
Der erste Ableitungsschritt sei von der Form $S\to AB$.
Da die Sprache endlich ist, kann man aus $A$ oder $B$ keine Satzform ableiten,
die die Variable $S$ enthält.
Daher ist nach Induktionannahme das längste Wort, das aus $A$ erzeugt
wird
höchstens $2^{n-2}$ Zeichen lang, und ebenso für $B$. (Man kann
$A$ als das Startsymbol einer neuen Grammatik auffassen, bei der alle
Regeln entfernt wurden, in denen $S$ vorkommt.)


\item [(59)]
Die Ableitung eines Wortes $w$ mit $|w|=n$ hat genau $2n-1$
Ableitungsschritte, für $n\ge1$.
Jede Regel der Form $A\to BC$ verlängert die Satzform um 1, daher
werden diese Regeln genau $(n-1)$-mal angewendet.
Außerdem muss man noch $n$ Regeln der Form $A\to a$ anwenden.
% \item [(62)]


\item [(62)]
Aus welchen Variablen kann man Terminalworte erzeugen? Aus $A$ und
$C$,
sodann aus $D$, $S$, und schließlich aus $S$. Die Variable $B$ ist überflüssig.
Somit kann man die Regeln $S\to AB$ und $C\to aB$ streichen.
Damit kann man aus $S$ nur noch Satzformen mit den Variablen
$C$ und $A$ erzeugen. Die Variablen $D$ und $E$ sind nicht erreichbar.
Die äquivalente Grammatik ohne überflüssige Variablen ist
$$S\to CA,\quad A\to a,\quad C\to c.$$



\item [(63)]
\noindent\quad
$
\openup 0,3\jot
\catcode`.=\active
\let.=\emptyset
\vtop{\halign{ &\strut\hbox to 6mm{\hss$#$\hss}\cr
   c&&d&&c&&c&&d\cr
\noalign{\hrule}
  C&&B,D&&C&&C&&D\cr
& S,D&&A&&.&&S,D\cr
&& C,A&&.&&S,D\cr
&&& .&&A,S\cr
&&&& C,A,S,D\cr
}\vss}
$


\item [(66a)] Der Automat ist ein binärer Zähler: Wenn man die Folge der
Kellerinhalte an den Übergängen von $q_0$ nach $q_1$ betrachtet, dann
wird von $0^n$ bis $1^n$ hochgezählt, wobei die niedrigwertigste
Stelle
ganz oben auf dem Stapel liegt.
Der Eingabekopf wird immer synchron mit dem Wachsen und Schrumpfen des
Kellers bewegt.
Bei Eingabe von $a^n$ benötigt der
Automat $2^{n+2}-2$ Schritte.

\noindent
\vbox{
\vbox{\def\q#1#2#3 {\hbox{$(q_#1,\Diamond\ifcase#2 
\or \underline \$
\fi,
#3Z_0)$}}
\q01 
\q11
\hbox{$(q_1,\Diamond\underline\$,\eps)$}
}

\medbreak

\vbox{
\def\q#1#2#3 {\hbox{$(q_#1,\Diamond\ifcase#2 
\or \underline a\$
\or a\underline \$
\fi,
#3Z_0)$}}
\q01 
\q020
\q120
\q021
\q121
\q11
\hbox{$(q_1,\Diamond\underline a\$,\eps)$}
}

\medbreak

\vbox{
\def\q#1#2#3 {\hbox{$(q_#1,\Diamond\ifcase#2 
\or \underline aa\$
\or a\underline a\$
\or aa\underline \$
\fi,
#3Z_0)$}}
\q01 
\q020
\q0300
\q1300
\q0310
\q1310
\q120
\q021
\q0301
\q1301
\q0311
\q1311
\q121
\q11

\hbox{$(q_1,\Diamond\underline aa\$,\eps)$}
}}
\qquad
%
\vbox{
\def\q#1#2#3 {\hbox{$(q_#1,\Diamond\ifcase#2 
\or \underline aaa\$
\or a\underline aa\$
\or aa\underline a\$
\or aaa\underline \$
\fi,
#3Z_0)$}}
\q01 
\q020
\q0300
\q04000
\q14000
\q04100
\q14100
\q1300
\q0310
\q04010
\q14010
\q04110
\q14110
\q1310
\q120
\q021
\q0301
\q04001
\q14001
\q04101
\q14101
\q1301
\q0311
\q04011
\q14011
\q04111
\q14111
\q1311
\q121
\q11
\hbox{$(q_1,\Diamond\underline aaa\$,\eps)$}
}


\item [(66b)]
Für $q\in Q$, $i\ge 1$, haben wir
\begin{eqnarray*}
  &&
E(q,i,0)=
E(q,i,1)= (q_1,i-1) \\
&&
E(q,i,Z_0)=
(q_1,i)
\end{eqnarray*}
 Für $i=0$ hängt die Entladefunktion davon ab, wie man
$\delta(\cdot,\cdot,\Diamond)$ definiert.
Wir können zum Beispiel
$\delta(q,\gamma,\Diamond)= \delta(q,\gamma,a)$ oder
$\delta(q,\gamma,\Diamond)= (q,\eps,N)$ setzen.


\item [(76)] Ja.
\item [(77)] Nein. Zum Beispiel ist die Sprache
$$
\{\,0 0^i1^{2i}\mid i\ge 1\,\} \cup
\{\,1 0^{2i}1^{i}\mid i\ge 1\,\}
$$
deterministisch kontextfrei, nicht aber ihre Umkehrung.

\end{itemize}


\end{document}