\documentclass{bschlangaul-aufgabe}
\bLadePakete{
  formale-sprachen,
  automaten,
  potenzmengen-konstruktion,
}
\begin{document}
\bAufgabenMetadaten{
  Titel = {Aufgabe 1},
  Thematik = {Komplemetieren eines NEA},
  Referenz = 46115-2019-H.T2-A1,
  RelativerPfad = Examen/46115/2019/09/Thema-2/Aufgabe-1.tex,
  ZitatSchluessel = examen:46115:2019:09,
  BearbeitungsStand = mit Lösung,
  Korrektheit = unbekannt,
  Ueberprueft = {unbekannt},
  Stichwoerter = {Potenzmengenalgorithmus, Nichtdeterministisch endlicher Automat (NEA), Deterministisch endlicher Automat (DEA)},
  EinzelpruefungsNr = 46115,
  Jahr = 2019,
  Monat = 09,
  ThemaNr = 2,
  AufgabeNr = 1,
}

\let\m=\bMenge

Es\index{Potenzmengenalgorithmus}
\footcite{examen:46115:2019:09} sei der nichtdeterministische endliche Automat
\bAutomat{
  alphabet={a, b},
  zustaende={1, 2, 3, 4, 5},
  ende={4, 5},
  start={1},
}
gegeben, wobei $\delta$ durch
folgenden Zeichnung beschrieben ist.
\footcite[Seite 17, Aufgabe 11]{theo:ab:1}
\index{Nichtdeterministisch endlicher Automat (NEA)}

\begin{center}
\begin{tikzpicture}[->,node distance=2cm]
\node[state,initial] (1) {1};
\node[state,above right of=1] (2) {2};
\node[state,below right of=1] (3) {3};
\node[state,right of=2,accepting] (4) {4};
\node[state,right of=3,accepting] (5) {5};

\path (1) edge[above,loop] node{a} (a);
\path (1) edge[below right] node{a} (2);
\path (1) edge[above] node{b} (3);
\path (3) edge[above,bend left] node{b} (5);
\path (3) edge[left] node{b} (2);
\path (4) edge[above left] node{a} (3);
\path (5) edge[above,bend left] node{b} (3);
\path (4) edge[right,bend left] node{b} (5);
\path (5) edge[right,bend left] node{a} (4);
\path (2) edge[above] node{b} (4);
\end{tikzpicture}
\end{center}

\noindent
Konstruieren Sie nachvollziehbar einen deterministischen endlichen
Automaten $A'$ , der das Komplement von $L(A)$ akzeptiert!
\index{Deterministisch endlicher Automat (DEA)}

\begin{bAntwort}
Zuerst mit Hilfe der Potenzmengenkonstruktion einen deterministischen
endlichen Automaten erstellen und dann die Zustände mit den Endzuständen
tauschen.

\def\z#1{
  \bZustandsMengenSammlung{#1}{
    {
      {0} {1}
      {1} {1,2}
      {2} {3}
      {3} {3,4}
      {4} {}
      {5} {2,5}
      {6} {4}
      {7} {5}
    }
  }
}
\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{1} & \z{3} \\
\s{2} & \z{2} & \z{4} & \z{5} \\
\s{3} & \z{3} & \z{2} & \z{5} \\
\s{4} & \z{4} & \z{4} & \z{4} \\
\s{5} & \z{5} & \z{6} & \z{3} \\
\s{6} & \z{6} & \z{2} & \z{7} \\
\s{7} & \z{7} & \z{6} & \z{2} \\
\end{tabular}

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

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

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

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

\node[state,left of=2,accepting]
(4) {\s{4}};

\node[state,right of=2]
(5) {\s{5}};

\node[state,below of=5]
(6) {\s{6}};

\node[state,below of=2]
(7) {\s{7}};

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

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

\path (2) edge[above] node{a} (4);
\path (2) edge[above] node{a} (5);

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

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

\path (5) edge[right] node{a} (6);
\path (5) edge[right,bend left] node{b} (3);

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

\path (7) edge[above,bend left] node{a} (6);
\path (7) edge[left] node{a} (2);
\end{tikzpicture}
\end{center}
\end{bAntwort}
\end{document}
