TU Wien:Formale Modellierung VU (Salzer)/Kapitel Endliche Automaten

Aus VoWi
Zur Navigation springen Zur Suche springen

Endliche Automaten besitzen nur endliche viele Zustände. Eingaben steuern in welchen Folgezustand vom Momentanzustand übergegangen wird.

Notation[Bearbeiten]

Formale Sprachen[Bearbeiten]

  • \Sigma ... Alphabet, d.h., endliche, nicht-leere Menge atomarer Symbole
  • w ... Wort über \Sigma, (endliche) Folge von Zeichen aus dem Alphabet \Sigma
  • \epsilon ... Leerwort
  • \Sigma^+ ... Menge aller nicht-leeren endlichen Wörter über \Sigma
  • \Sigma^* ... Menge aller endlichen Wörter über \Sigma (inklusive Leerwort)
  • w_1 \cdot w_2 = w_1 w_2 ... Verkettung zweier Wörter
  • L \subseteq \Sigma^* ... formale Sprache über \Sigma
  • 2^{\Sigma^*} ... Menge aller Sprachen über \Sigma

\langle\Sigma^*, \cdot, \epsilon\rangle bildet ein Monoid.

Endliche Automaten[Bearbeiten]

  • \delta^* die erweiterte Übergangsfunktion
  • L(A) die von A akzeptierte Sprache

Klassifikation[Bearbeiten]

deterministisch
Der Momentanzustand und die nächste Eingabe bestimmen eindeutig den Folgezustand.
nichtdeterministisch
Es gibt Zustände, die bei manchen Eingaben mehrere mögliche Folgezustände besitzen.

Klassischer endlicher Automat[Bearbeiten]

  • nur Eingaben (bzw. nur Ausgaben)
  • Anfangs- und Endzustände
  • verarbeitet endliche Symbolfolgen

A = \langle Q, \Sigma, \delta, q_0, F\rangle

  • Q ... Zustände
  • \Sigma ... Eingabealphabet
  • \delta(q, s) ... Übergangsfunktion/-relation, q \in Q, s \in \Sigma
  • q_0 \in Q ... Anfangszustand
  • F \subseteq Q ... Endzustände
deterministisch (DEA)
\delta : Q \times \Sigma \mapsto Q
\delta^*:Q\times \Sigma^* \mapsto Q
\delta^*(q,\epsilon) = q,\quad
\delta^*(q, sw) = \delta^*(\delta(q,s),w)\quad \forall q\in Q, s \in \Sigma, w\in \Sigma^*
nichtdeterministisch (NEA)
\delta \subseteq Q \times \Sigma \times Q
\delta \subseteq Q \times (\Sigma \cup \{\epsilon\}) \times Q

Transducer[Bearbeiten]

Wie endlicher Automat, aber mit Ein- und Ausgaben.

A = \langle Q, \Sigma, \Gamma, \delta, I, F\rangle

  • \Gamma ... Ausgabealphabet
  • I \subseteq Q ... Anfangszustände

Mealy- und Moore-Automaten sind deterministisch und verarbeiten in der Regel unendliche Symbolfolgen.

A = \langle Q, \Sigma, \Gamma, \delta, \gamma, q_0\rangle

  • \gamma ... Ausgabefunktion
  • I = \{q_0\}
Mealy-Automaten
\gamma
:Q \times \Sigma \mapsto \Gamma (Ausgaben sind mit Übergängen verknüpft)
Erweiterte Ausgabefunktion \gamma^*:Q\times \Sigma^* \mapsto \Gamma^*
Übersetzungsfunktion [A]\colon\Sigma^* \mapsto \Gamma^*
Moore-Automaten
\gamma
: Q \mapsto \Gamma (Ausgaben sind mit Zuständen verknüpft)

Büchi-Automaten[Bearbeiten]

Wie endlicher Automat, verarbeitet aber unendliche Symbolfolgen.

Modellierung[Bearbeiten]

graphische Spezifikation
Zustände sind Knoten, Übergänge sind Kanten, Ein- und Ausgaben sind Beschriftungen von Knoten und Kanten.
tabellarisch Spezifikation
Zu jedem Zustand und Eingabesymbol gibt es einen Eintrag mit zugehöriger Ausgabe und den Folgezuständen.
Vorgangsweise
  1. Was sind die Zustände des Systems? Wieviele sind notwendig? Zustandsbezeichnungen?
  2. Startzustand? Endzustände?
  3. Was sind die Aktionen/Eingaben, die zu Zustandsübergängen führen? Bezeichnung?
  4. Was sind die Aktionen/Ausgaben, die bei Zustandsübergängen stattfinden? Bezeichnung?
  5. Lege für jeden Zustand und jede Eingabe die Folgezustände und die Ausgaben fest.

Determinisierung[Bearbeiten]