\documentclass{bschlangaul-aufgabe}
\bLadePakete{formale-sprachen,mathe,automaten,potenzmengen-konstruktion}

\begin{document}
\bAufgabenMetadaten{
  Titel = {Aufgabe 1},
  Thematik = {Reguläre Sprache},
  Referenz = 66115-2007-H.T2-A1,
  RelativerPfad = Examen/66115/2007/09/Thema-2/Aufgabe-1.tex,
  ZitatSchluessel = examen:66115:2007:09,
  BearbeitungsStand = mit Lösung,
  Korrektheit = unbekannt,
  Ueberprueft = {unbekannt},
  Stichwoerter = {Reguläre Sprache, Reguläre Grammatik, Reguläre Ausdrücke, Potenzmengenalgorithmus},
  EinzelpruefungsNr = 66115,
  Jahr = 2007,
  Monat = 09,
  ThemaNr = 2,
  AufgabeNr = 1,
}

\let\z=\bZustandsmengeOhneMathe
\let\Z=\bZustandsmenge
\let\a=\bAlphabet
\let\f=\bUeberfuehrungsFunktionOhneMathe
\let\F=\bUeberfuehrungsFunktion

Gegeben sei der nichtdeterministische endliche Automat $M$ mit dem
Alphabet \a{a,b}, der Zustandsmenge \Z{z0, z1, z2, z3}, Anfangszustand
$z_0$, Endzustand \Z{z3} und der Überführungsfunktion $\delta$ mit:
\index{Reguläre Sprache}
\footcite{examen:66115:2007:09}

\begin{align*}
\f{z0, a} &= \z{z1, z2},\\
\f{z1, b} &= \z{z0, z1},\\
\f{z2, a} &= \z{z2, z3},\\
\f{z0, b} &= \f{z1, a} = \f{z2, b} = \f{z3, a} = \f{z3, b} = \emptyset\\
\end{align*}

\begin{bAntwort}
\begin{center}
\begin{tikzpicture}[->,node distance=4cm]
\node[state,initial]
(0) {$z_0$};

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

\node[state,below of=0]
(2) {$z_2$};

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

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

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

\path (1) edge[above,bend left] node{b} (0);
\path (1) edge[above,loop right] node{b} (1);

\path (2) edge[above,loop left] node{a} (2);
\path (2) edge[above] node{a} (3);

\path (0) edge[below left] node{b} (t);
\path (1) edge[below right] node{a} (t);
\path (2) edge[above left] node{b} (t);
\path (3) edge[above right] node{a,b} (t);
\end{tikzpicture}
\bFlaci{Afybo27zc}
\end{center}
\end{bAntwort}

\noindent
$L(M)$ sei die von $M$ akzeptierte Sprache.

\begin{enumerate}

%%
% a)
%%

\item Gelten folgende Aussagen?

\begin{enumerate}

%%
% i)
%%

\item Es gibt Zeichenreihen in $L(M)$, die genauso viele $a$’s enthalten
wie $b$’s.

\begin{bAntwort}
Ja, zum Beispiel das Wort $abbbaa$ oder $abbbbaaa$. Mit der
Überführungsfunktion $\f{z1, b} = \z{ z1 }$ können beliebig viele $b$’s
akzeptiert werden, sodass die Anzahl von $a$’s und $b$’s ausgeglichen
werden kann.
\end{bAntwort}

%%
% ii)
%%

\item Jede Zeichenreihe in $L(M)$, die mindestens vier $b$’s enthält,
enthält auch mindestens vier $a$’s.

\begin{bAntwort}
Nein, z. b. das Wort $abbbbaa$ wird akzeptiert. Ein Wort muss nur
mindestens drei $a$’s enthalten. Mit der Überführungsfunktion $\f{z1, b}
= \z{ z1 }$ können aber beliebig viele $b$’s akzeptiert werden.
\end{bAntwort}

\end{enumerate}

Begründen Sie Ihre Antworten.

%%
% b)
%%

\item Geben Sie eine reguläre (Typ-3-)Grammatik an, die $L(M)$ erzeugt.
\index{Reguläre Grammatik}

%%
% c)
%%

\item Beschreiben Sie $L(M)$ durch einen regulären Ausdruck.
\index{Reguläre Ausdrücke}

\begin{bAntwort}
(ab+)*aa+
\end{bAntwort}

%%
% d)
%%

\item Konstruieren Sie aus M mit der Potenzmengen-Konstruktion (und
entsprechender Begründung) einen deterministischen endlichen Automaten,
der $L(M)$ akzeptiert.
\index{Potenzmengenalgorithmus}

\begin{bAntwort}
\def\z#1{
  \bZustandsMengenSammlungNr{#1}{
    {
      {0} {0}
      {1} {1,2}
      {2} {t}
      {3} {2,3,t}
      {4} {0,1,t}
      {5} {1,2,t}
    }
  }
}
\let\s=\bZustandsnameGross

\begin{tabular}{l|l|l|l}
Name & Zustandsmenge & Eingabe a & Eingabe b \\\hline\hline
\s{0} & \z{0} & \z{1} & \z{2} \\
\s{1} & \z{1} & \z{3} & \z{4} \\
\s{2} & \z{2} & \z{2} & \z{2} \\
\s{3} & \z{3} & \z{3} & \z{2} \\
\s{4} & \z{4} & \z{5} & \z{4} \\
\s{5} & \z{5} & \z{3} & \z{4} \\
\end{tabular}

\begin{center}
\begin{tikzpicture}[->,node distance=2cm,y=-1cm]
\node[state]
(0) at (0,0) {\s{0}};

\node[state]
(1) at (2,0) {\s{1}};

\node[state]
(2) at (0,2) {\s{2}};

\node[state,accepting]
(3) at (2,2) {\s{3}};

\node[state]
(4) at (4,0) {\s{4}};

\node[state]
(5) at (4,2) {\s{5}};

\path (0) edge[above] node{a} (1);
\path (0) edge[left] node{b} (2);

\path (1) edge[left] node{a} (3);
\path (1) edge[above] node{b} (4);

\path (2) edge[above,loop left] node{a,b} (2);

\path (3) edge[above,loop below] node{a} (3);
\path (3) edge[above] node{b} (2);

\path (4) edge[right,bend left] node{a} (5);
\path (4) edge[above,loop right] node{b} (4);

\path (5) edge[above] node{a} (3);
\path (5) edge[left,bend left] node{b} (4);
\end{tikzpicture}
\bFlaci{Aig9i4u7z}
\end{center}
\end{bAntwort}

\end{enumerate}
\end{document}