%% -*- mode: latex; TeX-master: "compilerbau.tex"; -*-

\begin{slide}{Endliche Automaten}

\kopf{$ $Id: auto.tex,v 1.1 2011-10-16 14:06:16 waldmann Exp $ $}

Intern stellt man reguläre Sprachen lieber effizienter dar:

Ein (nichtdeterministischer) endlicher Automat $A$
ist ein Tupel $(Q, S, F, T)$ mit

\begin{tabular}{l|l}
\begin{minipage}{0.5\textwidth}
\begin{itemize}\itemsep 0pt \raggedright
\item endlicher Menge $Q$ (Zustände)
\item Menge $S \subseteq Q$ (Start-Zustände)
\item Menge $F \subseteq Q$ (akzeptierende Zustände)
\item Relation $T \subseteq (Q \times \Sigma \times Q)$ 
\end{itemize}
\end{minipage}
&
\begin{minipage}{0.47\textwidth}
autotool:
\begin{small}
\begin{verbatim}
NFA { alphabet = mkSet "ab"
  , states = mkSet [ 1, 2, 3]
  , starts = mkSet [ 2]
  , finals = mkSet [ 2]
  , trans = collect
    [ (1, 'a', 2)
    , (2, 'a', 1)
    , (2, 'b', 3)
    , (3, 'b', 2)
    ]
  }
\end{verbatim}
\end{small}
\end{minipage}
\end{tabular}

\end{slide}

\begin{slide}{Rechnungen und Sprachen von Automaten}

Für $(p,c,q)\in T(A)$ schreiben wir auch $p \stackrel{c}{\to}_A q$.

Für ein Wort $w = c_1 c_2 \ldots c_n$ 
und Zustände $p_0, p_1, \ldots, p_n$
mit 
\[ p_0 \stackrel{c_1}{\to}_A p_1 \stackrel{c_2}{\to}_A \ldots
\stackrel{c_n}{\to}_A p_n \]
schreiben wir $p_0 \stackrel{w}{\to}_A p_n$.

(es gibt in $A$ einen mit $w$ beschrifteten Pfad  von $p_0$ nach $p_n$).

Die von $A$ \emph{akzeptierte} Sprache ist 
\[ L(A) = \{ w \mid \exists p_0\in S, p_n\in F: p_0 \stackrel{w}{\to}_A p_n \}
\]

(die Menge aller Wörter $w$, für die es in $A$ einen 
akzeptierenden Pfad von einem Start- zu einem akzeptierenden Zustand gibt)



\end{slide}
