automaten.tex 1.91 KB
Newer Older
1
2
\section{Automaten \hfill {\small 10 Punkte}}

3
\begin{enumerate}[a)]
4
5
\item Gegeben sei der folgende nichtdeterminischtische endliche Automat
  $A_1$ mit $\Sigma = \left\{ a, b, c \right\}$:
6
  \begin{center}
7
8
9
10
    \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$}; %
11

12
13
14
15
16
17
18
19
      \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}
  
20
21
22
  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
23
24
25
26
27
28
29
30
31
  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$}; %
32

33
34
35
36
37
    \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);
38
  \end{tikzpicture}
39
  \end{center}
40
41

  Stellen sie zu diesem ein Gleichungssystem auf:
42
  \begin{align*}
43
    \Large
44
45
46
47
    A & = 0\,B \\
    B & = \\
    C & =
  \end{align*}
48
  
49
50
\item Lößen sie das obige Gleichungssystem und geben sie an welche
  Variable den regulären Ausdruck beschreibt. 
51
52
53
54
55
56
\end{enumerate}

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