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

\begin{document}
\bAufgabenMetadaten{
  Titel = {Aufgabe 1},
  Thematik = {NEA und Minimalisierung},
  Referenz = 66115-2012-H.T1-A1,
  RelativerPfad = Examen/66115/2012/09/Thema-1/Aufgabe-1.tex,
  ZitatSchluessel = theo:ab:1,
  ZitatBeschreibung = {Aufgabe 6},
  BearbeitungsStand = mit Lösung,
  Korrektheit = unbekannt,
  Ueberprueft = {unbekannt},
  Stichwoerter = {Potenzmengenalgorithmus, Minimierungsalgorithmus},
  EinzelpruefungsNr = 66115,
  Jahr = 2012,
  Monat = 09,
  ThemaNr = 1,
  AufgabeNr = 1,
}

\def\z#1{$z_#1$}
\let\f=\bFussnote
\let\k=\bAutomatenKante
\let\l=\bLeereZelle
\let\Z=\bZustandsPaar

Wir fixieren das Alphabet \bAlphabet{a, b} und definieren $L
\subseteq \Sigma^*$ durch\index{Potenzmengenalgorithmus}
\footcite[Aufgabe 6]{theo:ab:1}

\begin{center}
\bAusdruck{w}{\text{in } w \text{ kommt das Teilwort \texttt{bab} vor}}
\end{center}

\noindent
\zB ist \texttt{babaabb} $\in L$, aber
\texttt{baabaabb} $\notin L$. Der folgende nichtdeterministische
Automat $A$ erkennt $L$:\footcite{examen:66115:2012:09}

\begin{center}
\begin{tikzpicture}[->,node distance=2cm]
\node[state,initial] (0) {$z_0$};
\node[state,right of=0] (1) {$z_1$};
\node[state,right of=1] (2) {$z_2$};
\node[state,right of=2,accepting] (3) {$z_3$};

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

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

\path (3) edge[loop,above] node{a,b} (3);
\end{tikzpicture}
\bFlaci{Af75jwj3r}
\end{center}

\begin{enumerate}
\item Wenden Sie die Potenzmengenkonstruktion auf den Automaten an und
geben Sie den resultierenden deterministischen Automaten an. Nicht
erreichbare Zustände sollen nicht dargestellt werden.

\begin{bAntwort}

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

\begin{tabular}{l|l|l}
Zustandsmenge & Eingabe a & Eingabe b \\\hline
\z0 & \z0 & \z1 \\
\z1 & \z2 & \z1 \\
\z2 & \z0 & \z3 \\
\z3 & \z4 & \z3 \\
\z4 & \z5 & \z3 \\
\z5 & \z5 & \z3\\
\end{tabular}

\begin{center}
\def\Z#1{$Z_{#1}$}
\begin{tikzpicture}[->,node distance=2cm]
\node[state,initial] (0) {\Z0};
\node[state,above right of=0] (1) {\Z1};
\node[state,below right of=1] (2) {\Z2};
\node[state,below of=2,accepting] (3) {\Z3};
\node[state,left of=3,accepting] (4) {\Z4};
\node[state,below of=4,accepting] (5) {\Z5};

\k 0 0 a {above,loop below}
\k 0 1 b {above}
\k 1 2 a {above}
\k 1 1 b {above,loop}
\k 2 0 a {above}
\k 2 3 b {right}
\k 3 4 a {above,bend left}
\k 3 3 b {above,loop right}
\k 4 5 a {left}
\k 4 3 b {above,bend left}
\k 5 5 a {above,loop left}
\k 5 3 b {above}
\end{tikzpicture}
\bFlaci{Aro483e89}
\end{center}

\end{bAntwort}

\item Konstruieren Sie aus dem so erhaltenen deterministischen Automaten
den Minimalautomaten für $L$. Beschreiben Sie dabei die Arbeitsschritte
des verwendeten Algorithmus in nachvollziehbarer Weise.
\index{Minimierungsalgorithmus}

\begin{bAntwort}
\begin{center}
\begin{tabular}{|c||c|c|c|c|c|c|}
\hline
\z0 & \l  & \l  & \l  & \l  & \l & \l  \\ \hline
\z1 & \f3 & \l  & \l  & \l  & \l & \l  \\ \hline
\z2 & \f2 & \f2 & \l  & \l  & \l & \l  \\ \hline
\z3 & \f1 & \f1 & \f1 & \l  & \l & \l  \\ \hline
\z4 & \f1 & \f1 & \f1 &     & \l & \l  \\ \hline
\z5 & \f1 & \f1 & \f1 &     &    & \l  \\ \hline\hline
    & \z0 & \z1 & \z2 & \z3 & \z4& \z5 \\ \hline
\end{tabular}
\end{center}

\bFussnoten

\begin{liUebergangsTabelle}{a}{b}
\Z01 & \Z02\f3 & \Z11 \\
\Z02 & \Z00 & \Z13\f2 \\
\Z12 & \Z20\f3 & \Z13\f2 \\
\Z34 & \Z45 & \Z33 \\
\Z35 & \Z45 & \Z33 \\
\Z45 & \Z55 & \Z33 \\
\end{liUebergangsTabelle}

\def\Z#1{$Z_{#1}$}
\begin{tikzpicture}[->,node distance=2cm]
\node[state,initial] (0) {\Z0};
\node[state,above right of=0] (1) {\Z1};
\node[state,below right of=1] (2) {\Z2};
\node[state,right of=2,accepting] (345) {\Z{345}};

\k 0 0 a {above,loop below}
\k 0 1 b {above left}
\k 1 2 a {above right}
\k 1 1 b {above,loop}
\k 2 0 a {above}
\k 2 {345} b {above}
\k {345} {345} {a,b} {above,loop below}
\end{tikzpicture}
\bFlaci{Ar3joif5z}
\end{bAntwort}
\end{enumerate}

\end{document}