\documentclass{bschlangaul-aufgabe}
\bLadePakete{formale-sprachen,automaten,potenzmengen-konstruktion}
\begin{document}
\bAufgabenMetadaten{
  Titel = {Aufgabe 2},
  Thematik = {Automaten mit Zuständen q, r, s, t},
  Referenz = 66115-2020-F.T1-A2,
  RelativerPfad = Examen/66115/2020/03/Thema-1/Aufgabe-2.tex,
  ZitatSchluessel = examen:66115:2020:03,
  BearbeitungsStand = mit Lösung,
  Korrektheit = unbekannt,
  Ueberprueft = {unbekannt},
  Stichwoerter = {Reguläre Sprache, Potenzmengenalgorithmus},
  EinzelpruefungsNr = 66115,
  Jahr = 2020,
  Monat = 03,
  ThemaNr = 1,
  AufgabeNr = 2,
}

\def\z#1{
  \bZustandsMengenSammlungNr{#1}{
    {
      {0} {0}
      {1} {0,1}
      {2} {0,2}
      {3} {0,2,3}
      {4} {0,1,2}
    }
  }
}

\begin{enumerate}
%%
% (a)
%%

\item Es sei $L \subseteq \{ a, b, c \}^*$ die von dem folgenden
nichtdeterministischen Automaten akzeptierte Sprache:
\index{Reguläre Sprache}
\footcite{examen:66115:2020:03}

\begin{center}
\begin{tikzpicture}[li automat]
  \node[state,initial] (z0) at (2.14cm,-2.14cm) {$z_0$};
  \node[state] (z1) at (4cm,-2.14cm) {$z_1$};
  \node[state] (z2) at (5.71cm,-2.14cm) {$z_2$};
  \node[state,accepting] (z3) at (7.57cm,-2.14cm) {$z_3$};

  \path (z0) edge[auto] node{$b$} (z1);
  \path (z0) edge[auto,loop above] node{$a,b,c$} (z0);
  \path (z1) edge[auto] node{$c$} (z2);
  \path (z2) edge[auto] node{$a$} (z3);
  \path (z2) edge[auto,loop above] node{$a,b,c$} (z2);
\end{tikzpicture}
\end{center}
\bFlaci{Apmac9bwc}

Beschreiben Sie (in Worten) wie die Wörter aus der Sprache $L$ aussehen.

\begin{bAntwort}
Alle Wörter der Sprache $L$ enthalten die Symbolfolge $bc$ und enden auf
$a$. Am Anfang der Wörter und vor dem letzten $a$ können beliebige
Kombination aus $a,b,c$ vorkommen.
\end{bAntwort}

%%
% (b)
%%

\item Benutzen Sie die Potenzmengenkonstruktion, um einen
deterministischen Automaten zu konstruieren, der zu dem Automaten aus
Teil (a) äquivalent ist. (Berechnen Sie nur erreichbare Zustände.)
\index{Potenzmengenalgorithmus}

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

\begin{center}
\begin{tikzpicture}[li automat]
  \node[state,initial] (Z0) at (1.86cm,-1.71cm) {$Z_0$};
  \node[state] (Z1) at (2cm,-5.86cm) {$Z_1$};
  \node[state] (Z4) at (8.86cm,-2cm) {$Z_4$};
  \node[state,accepting] (Z3) at (3.71cm,-1.86cm) {$Z_3$};
  \node[state] (Z2) at (8.29cm,-5.86cm) {$Z_2$};

  \path (Z0) edge[auto,bend left=10] node{$b$} (Z1);
  \path (Z0) edge[auto,loop above] node{$a,c$} (Z0);
  \path (Z1) edge[auto,bend left=10] node{$a$} (Z0);
  \path (Z1) edge[auto,loop below] node{$b$} (Z1);
  \path (Z1) edge[auto] node{$c$} (Z2);
  \path (Z2) edge[auto,bend left=10] node{$a$} (Z3);
  \path (Z2) edge[auto,bend left=10] node{$b$} (Z4);
  \path (Z2) edge[auto,loop below] node{$c$} (Z2);
  \path (Z3) edge[auto,bend left=10] node{$b$} (Z4);
  \path (Z3) edge[auto,bend left=10] node{$c$} (Z2);
  \path (Z3) edge[auto,loop above] node{$a$} (Z3);
  \path (Z4) edge[auto,bend left=10] node{$a$} (Z3);
  \path (Z4) edge[auto,bend left=10] node{$c$} (Z2);
  \path (Z4) edge[auto,loop above] node{$b$} (Z4);
\end{tikzpicture}
\end{center}
\bFlaci{A5o6pho8c}

\end{bAntwort}

%%
% (c)
%%

\item Ist der resultierende deterministische Automat schon minimal?
Begründen Sie Ihre Antwort.

\begin{bAntwort}
Nein. \z2 und \z4 können vereinigt werden, da sie bei denselben Eingaben
auf die selben Potzenmengen übergehen.

\begin{tabular}{l|l|l|l}
Zustandsmenge & Eingabe $a$ & Eingabe $b$ & Eingabe $c$ \\\hline
\z2 & \z3 & \z4 & \z2 \\
\z3 & \z3 & \z4 & \z2 \\
\z4 & \z3 & \z4 & \z2 \\
\end{tabular}

\begin{center}
\begin{tikzpicture}[li automat]
  \node[state,initial] (Z0) at (2.14cm,-2.14cm) {$Z_0$};
  \node[state] (Z1) at (4.57cm,-2.14cm) {$Z_1$};
  \node[state,accepting] (Z3) at (8.86cm,-2.14cm) {$Z_3$};
  \node[state] (Z24) at (6.57cm,-2.14cm) {$Z_{24}$};

  \path (Z0) edge[auto,bend left] node{$b$} (Z1);
  \path (Z0) edge[auto,loop above] node{$a,c$} (Z0);
  \path (Z1) edge[auto,loop above] node{$b$} (Z1);
  \path (Z1) edge[auto,bend left] node{$a$} (Z0);
  \path (Z1) edge[auto] node{$c$} (Z24);
  \path (Z3) edge[auto,bend left] node{$b,c$} (Z24);
  \path (Z3) edge[auto,loop above] node{$a$} (Z3);
  \path (Z24) edge[auto,loop above] node{$b,c$} (Z24);
  \path (Z24) edge[auto,bend left] node{$a$} (Z3);
\end{tikzpicture}
\end{center}
\bFlaci{Ai1hox2b7}
\end{bAntwort}

%%
% (d)
%%

\item Minimieren Sie den folgenden deterministischen Automaten:

\end{enumerate}
\end{document}