Dies ist eine alte Version des Dokuments!

Automatentheorie

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.

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)