Dies ist eine alte Version des Dokuments!

Inhaltsverzeichnis

Automatentheorie
- Einleitung
- Deterministische endliche Automaten (DEA)
  - Sprache eines DEA

Automatentheorie

Einleitung

Einordung "Automatentheorie"
- Formalisierung reaktiver Systeme (diskrete Systeme)
- diskrete Systeme (Automatentheorie) ∈ kontinuierliche Systeme ∈ technische Kybernetik ∈ Kybernetik (Wissenschaft von der Funktion komplexer Systeme)
Funktion endlicher Automaten: Eingaben → (innere) Zustände → Ausgaben
Klassifizierung
- Endliche erkennende Automaten
  - am weitesten reduzierte Automaten
  - keine Äußerungen nach außen
- nächste Stufe: minimale Reaktion (binär, z.B. Lampe an/aus)
Eingaben: Zeichenfolgen über Alphabet X = { x₁, x₂, …, x_n }
- werden akzeptiert, wenn Automat im Endzustand ist
Ausgaben: Zeichenfolgen über Alphabet Y = { y₁, y₂, …, y_n }
Zustände (states): unterscheidbare Stadien der Verarbeitung von Eingaben
- Zustandsmenge S = { s₁, s₂, …, s_n }
- Partizipien weisen auf Zustände hin: "Taste gedrückt" etc.

Deterministische endliche Automaten (DEA)

Definition: A = (X, S, s₀, δ, F)

X: Eingabealphabet
S: Zustandsmenge
s₀: Anfangszustand

δ: Zustandsübergangsfunktion

S x X → S

δ(s_i, x_j) → s_k (Folgezustand zu s_i)

* δ<sup>*</sup>: Fortsetzung der Zustandsübergangsfunktion auf Wörter ∈ X<sup>*</sup>
  * δ<sup>*</sup>(s<sub>0</sub>, w) ∈ S | w = x<sub>1</sub>, x<sub>2</sub>, ..., x<sub>n</sub>, x<sub>i</sub> ∈ X
  * δ<sup>*</sup>(s, ε) = s | s ∈ S, ε leeres Wort
  * δ<sup>*</sup>(s, x<sub>i</sub>) = δ(s, x<sub>i</sub>) | x<sub>i</sub> ∈ X, **ein** Zeichen
  * δ<sup>*</sup>(s, x) = δ<sup>*</sup>(s, x<sub>1</sub>x<sub>2</sub>...x<sub>n</sub>) = δ<sup>*</sup>(δ(s, x<sub>1</sub>), x<sub>2</sub>x<sub>3</sub>...x<sub>n</sub>)

* Im DEA gibt es für jeden Zustand für jedes Eingabezeichen eine Transition in seinen Folgezustand!

Sprache eines DEA

L(A) := { w ∈ X^{</sup> | δ^*(s₀, w) ∈ F} (Menge aller Wörter, die vom Anfangszustand in einen Endzustand führen)
* durch endliche Automaten akzeptierbar/definierbar, falls es einen DEA gibt, der sie akzeptiert

===== Nicht-deterministische endliche Automaten (NEA) =====
* Definition: A = (X, S, S₀, δ, F)
* X: Eingabealphabet
* S: Zustandsmenge
* S₀: Menge der Anfangszustände, S₀ ⊆ S
* δ: Zustandsübergangsfunktion
* S x X → P(S), zu einem Eingabesymbol ist in einem definierten Zustand eine Menge von Folgezuständen möglich
* δ(s_i, x_j) → S_k (Folgezustände zu s_i, leere Menge, ein oder mehrere Zustände)

===== ToDo =====
* Skript Herold lesen}

Stefans Wiki

Benutzer-Werkzeuge

Webseiten-Werkzeuge

**Dies ist eine alte Version des Dokuments!**