\documentclass{bschlangaul-aufgabe}
\bLadePakete{formale-sprachen,automaten,minimierung,syntax,potenzmengen-konstruktion,pumping-lemma}
\begin{document}
\bAufgabenMetadaten{
  Titel = {Aufgabe 1},
  Thematik = {Alphabet „01“ Anzahl Unterschied höchstes 3},
  Referenz = 66115-2015-F.T1-A1,
  RelativerPfad = Examen/66115/2015/03/Thema-1/Aufgabe-1.tex,
  ZitatSchluessel = examen:66115:2015:03,
  BearbeitungsStand = mit Lösung,
  Korrektheit = unbekannt,
  Ueberprueft = {unbekannt},
  Stichwoerter = {Reguläre Sprache, Pumping-Lemma (Reguläre Sprache), Potenzmengenalgorithmus},
  EinzelpruefungsNr = 66115,
  Jahr = 2015,
  Monat = 03,
  ThemaNr = 1,
  AufgabeNr = 1,
}

\let\l=\bLeereZelle
\let\f=\bFussnote
\def\z#1{
  \bZustandsMengenSammlungNr{#1}{
    {
      {0} {0}
      {1} {0,1}
      {2} {0,2}
      {3} {0,1,2}
    }
  }
}
\let\s=\bZustandsnameGross
\let\Z=\bZustandsPaar

% verbessert 30.3.2021

Die\index{Reguläre Sprache} \footcite{examen:66115:2015:03} Sprache $L$
über den Alphabet \bAlphabet{0, 1} enthält alle Wörter, bei denen beim
Lesen von links nach rechts der Unterschied in der Zahl der $0$en und
$1$en stets höchstens $3$ ist. Also ist $w \in L$ genau dann, wenn für
alle $u$, $v$ mit $w = uv$ gilt $||u|_0 - |u|_1| \leq 3$. Erinnerung:
$|w|_a$ bezeichnet die Zahl der $a$’s im Wort $w$.
\footcite[Aufgabe 10]{theo:ab:1}

\begin{enumerate}

%%
% (a)
%%

\item Sei $A = (Q, \Sigma, \delta, q_0 , E)$ ein deterministischer
endlicher Automat für $L$. Es sei $w_1 = 111$, $w_2 = 11$, $w_3 = 1$, $
w_4 = \varepsilon$, $w_5 = 0$, $w_6 = 00$, $w_7 = 000$. Machen Sie sich
klar, dass der Automat jedes dieser Wörter verarbeiten können muss.
Folgern Sie, dass der Automat mindestens sieben Zustände haben muss.
Schreiben Sie Ihr Argumentation schlüssig und vollständig auf.

\begin{bAntwort}
Ein deterministischer endlicher Automat hat keinen zusätzlichen Speicher
zur Verfügung, in dem die Anzahl der bisher vorkommenden Einsen und
Nullen gespeichert werden könnte. Ein deterministischer endlicher
Automat kann die von der Sprache benötigten Anzahl an Einsen und Nullen
nur in Form von Zustanden speichern. Um die Anzahl von $3$ Einsen bzw.
$3$ Nullen zu speichern, sind also 6 Zustände nötig.

Die Wörter $01$ oder $0011$ oder $0101$ etc. haben eine Differenz von
$0$, wenn die Anzahl an Nullen und Einsen abzogen wird. Um auch diese
Wörter darstellen zu können, ist mindestens ein weiterer Zustand nötig.
\end{bAntwort}

%%
% (b)
%%

\item Begründen Sie, dass $L$ regulär ist.

\begin{bAntwort}
\begin{center}
\begin{tikzpicture}[li automat,node distance=2cm]
\node[state,initial,accepting]
(0) {$z_0$};

\node[state,above right of=0,accepting]
(1) {$z_1$};

\node[state,right of=1,accepting]
(2) {$z_2$};

\node[state,right of=2,accepting]
(3) {$z_3$};

\node[state,below right of=0,accepting]
(4) {$z_4$};

\node[state,right of=4,accepting]
(5) {$z_5$};

\node[state,right of=5,accepting]
(6) {$z_6$};

\node[state,below right of=3]
(t) {$z_t$};

\path (0) edge[above,bend left] node{0} (1);
\path (1) edge[above,bend left] node{0} (2);
\path (2) edge[above,bend left] node{0} (3);

\path (1) edge[above,bend left] node{1} (0);
\path (2) edge[above,bend left] node{1} (1);
\path (3) edge[above,bend left] node{1} (2);

\path (0) edge[above,bend left] node{1} (4);
\path (4) edge[above,bend left] node{1} (5);
\path (5) edge[above,bend left] node{1} (6);

\path (4) edge[above,bend left] node{0} (0);
\path (5) edge[above,bend left] node{0} (4);
\path (6) edge[above,bend left] node{0} (5);

\path (3) edge[above] node{0} (t);
\path (6) edge[above] node{1} (t);
\path (t) edge[loop right] node{0,1} (t);

\end{tikzpicture}
\bFlaci{Ait6va31c}
\end{center}
\end{bAntwort}

%%
% (c)
%%

\item Jemand behauptet, diese Sprache sei nicht regulär und gibt
folgenden „Beweis“ dafür an: Wäre $L$ regulär, so sei $n$ eine
entsprechende Pumping-Zahl. Nun ist $w = (01)^n \in L$. Zerlegt man nun
$w = uxv$, wobei $u = 0$, $x = 1$, $v = (01)^{n-1}$ , so ist zum Beispiel
$ux^5 v \notin L$, denn es ist $ux^5 v = 01111101010101$.... Legen Sie
genau dar, an welcher Stelle dieser „Beweis” fehlerhaft ist.
\index{Pumping-Lemma (Reguläre Sprache)}

\begin{bExkurs}[Pumping-Lemma für Reguläre Sprachen]
\bPumpingRegulaer
\end{bExkurs}

\begin{bAntwort}
Das Wort $(01)^n$ wurde falsch zerlegt. Für die Pumping-Zahl $n = 3$
gibt es sehr wohl eine Zerlegung, die beim Aufpumpen regulär ist, also:
$\omega = 010101$ ($u = 01$, $x = 01$ und $v = 01$). $ux^5 v = 01
0101010101 01 \in L$. Es gibt also eine Zerlegung, die beim Aufpumpen
die 3 Pumping-Lemma-Eigenschaften erfüllt. Daher kann man das
Pumping-Lemma so nicht widerlegt werden, indem man ein einziges
Gegenbeispiel gibt.
\end{bAntwort}

%%
% (d)
%%

\item In anderen Fällen können nichtdeterministische endliche Automaten
echt kleiner sein als die besten deterministischen Automaten. Ein
Beispiel ist die Sprache $L_2 = \Sigma^* 1 \Sigma$ aller Wörter, deren
vorletztes Symbol $1$ ist. Geben Sie einen nicht-deterministischen
Automaten mit nur drei Zuständen an, $L_2$ erkennt.

\begin{bAntwort}
\begin{center}
\begin{tikzpicture}[li automat,node distance=3cm]
\node[state,initial]
(0) {$z_0$};

\node[state,right of=0]
(1) {$z_1$};

\node[state,right of=1,accepting]
(2) {$z_2$};

\path (0) edge[above,loop] node{$0$,$1$} (0);
\path (0) edge[above] node{$1$} (1);
\path (1) edge[above] node{$0$,$1$} (2);
\end{tikzpicture}
\bFlaci{Apwzjufbg}
\end{center}
\end{bAntwort}

%%
% (e)
%%

\item Führen Sie auf Ihrem Automaten die Potenzmengenkonstruktion und
anschließend den Minimierungsalgorithmus durch. Wie viele Zustände
muss ein deterministischer Automat für $L_2$ also mindestens haben?
\index{Potenzmengenalgorithmus}

\begin{bAntwort}

%%
%
%%

\bPseudoUeberschrift{Potenzmengenkonstruktion}

\begin{tabular}{l|l|l|l}
Name & Zustandsmenge & Eingabe $0$ & Eingabe $1$ \\\hline\hline
\s0 & \z0 & \z0 & \z1 \\
\s1 & \z1 & \z2 & \z3 \\
\s2 & \z2 & \z0 & \z1 \\
\s3 & \z3 & \z2 & \z3 \\
\end{tabular}

\begin{center}
\begin{tikzpicture}[li automat,node distance=3cm]
\node[state,initial]
(0) {\s0};

\node[state,below of=0]
(1) {\s1};

\node[state,right of=0,accepting]
(2) {\s2};

\node[state,right of=1,accepting]
(3) {\s3};

\path (0) edge[above,loop] node{$0$} (0);
\path (0) edge[left] node{$1$} (1);
\path (1) edge[above,bend left] node{$0$} (2);
\path (1) edge[above] node{$1$} (3);
\path (2) edge[above] node{$0$} (0);
\path (2) edge[above,bend left] node{$1$} (1);
\path (3) edge[right] node{$0$} (2);
\path (3) edge[above,loop below] node{$1$} (3);
\end{tikzpicture}
\bFlaci{Ajfcofpb9}
\end{center}

%%
%
%%

\bPseudoUeberschrift{Minimierungsalgorithmus}

\begin{center}
\begin{tabular}{|c||c|c|c|c|}
\hline
\s0 & \l  & \l  & \l  & \l  \\ \hline
\s1 & \f2 & \l  & \l  & \l  \\ \hline
\s2 & \f1 & \f1 & \l  & \l  \\ \hline
\s3 & \f1 & \f1 & \f2 & \l  \\ \hline\hline
    & \s0 & \s1 & \s2 & \s3 \\ \hline
\end{tabular}
\end{center}

\bFussnoten

\def\bZustandsPaarVariablenName{Z}

\begin{liUebergangsTabelle}{0}{1}
\Z01 & \Z02 \f2 & \Z13 \f2 \\
\Z23 & \Z01 & \Z13 \f2 \\
\end{liUebergangsTabelle}

Wie aus der oben stehenden Tabelle abzulesen ist, gibt es keine
äquivalenten Zustände. Der Automat kann nicht minimiert werden. Er ist
bereits minimal.

\end{bAntwort}
\end{enumerate}
\end{document}