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

1. Aussagenlogik
2. Endliche Automaten
3. Formale Sprachen und Grammatiken
4. Prädikatenlogik
5. Petri-Netze

Diese Seite ist noch nicht fertig!

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

Notation

Formale Sprachen

• $\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

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

Klassifikation

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

• 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

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

Wie endlicher Automat, verarbeitet aber unendliche Symbolfolgen.

Modellierung

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.