\section{Automaten \hfill {\small 10 Punkte}}

\begin{enumerate}[a)]
\item Gegeben sei der folgende nichtdeterminischtische endliche Automat
  $A_1$ mit $\Sigma = \left\{ a, b, c \right\}$:
  \begin{center}
    \begin{tikzpicture}[->, shorten >= 1pt, node distance = 2cm, on grid]
      \node[state, initial]           (q0) {$q_0$}; %
      \node[state]                    (q1) [right of=q0] {$q_1$}; %
      \node[state, accepting]         (q2) [right of=q1] {$q_2$}; %

      \path
      (q0) edge [loop above]          node {$a \;|\; b$} (q0)
      (q0)  edge [above]               node {$b$} (q1)
      (q1) edge [above]               node {$a$} (q2)
      (q2) edge [loop above]          node {$a \;|\; b \;|\; c$} (q2);
    \end{tikzpicture}
  \end{center}
  
  Konstruieren Sie mit dem Verfahren aus der Vorlesung (es muß erkennbar
  sein!) eines zu $A_1$ einen äqivalenten deterministischen endlichen
  Automaten. Zeichnen sie nur die vom Startzusatand erreichbaren
  Zustände, diese aber alle. Führen Sie keine "`Vereinfachungen"' durch.

\item Gegeben sei der folgende nichtdeterminischtische endliche Automat
  $A_2$ über $\Sigma = \left\{ 0, 1 \right\}$:
  \begin{center}
  \begin{tikzpicture}[->, shorten >= 1pt, node distance = 2cm, on grid]
    \node[state, initial] (a) {$A$}; %
    \node[state] (b) [right of=a] {$B$}; %
    \node[state, accepting] (c) [right of=b] {$C$}; %

    \path
    (a) edge [above] node {0} (b)
    (b) edge [loop above] node {0 \;|\; 1} (b)
    (b) edge [above,bend left] node {0} (c)
    (c) edge [above,bend left] node {1} (b);
  \end{tikzpicture}
  \end{center}

  Stellen sie zu diesem ein Gleichungssystem auf:
  \begin{align*}
    \Large
    A & = 0\,B \\
    B & = \\
    C & =
  \end{align*}
  
\item Lößen sie das obige Gleichungssystem und geben sie an welche
  Variable den regulären Ausdruck beschreibt. 
\end{enumerate}

%%% Local Variables:
%%% mode: latex
%%% TeX-master: "master"
%%% End: