Benutzer-Werkzeuge

Webseiten-Werkzeuge


se:automatentheorie

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

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 = { x1, x2, …, xn }
    • werden akzeptiert, wenn Automat im Endzustand ist
  • Ausgaben: Zeichenfolgen über Alphabet Y = { y1, y2, …, yn }
  • Zustände (states): unterscheidbare Stadien der Verarbeitung von Eingaben
    • Zustandsmenge S = { s1, s2, …, sn }
    • Partizipien weisen auf Zustände hin: "Taste gedrückt" etc.

Deterministische endliche Automaten (DEA)

  • Definition: A = (X, S, s0, δ, F)
    • X: Eingabealphabet
    • S: Zustandsmenge
    • s0: Anfangszustand
    • δ: Zustandsübergangsfunktion
      • S x X → S
      • δ(si, xj) → sk (Folgezustand zu si)
        * δ<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>) 

ToDo

  • Skript Herold lesen
se/automatentheorie.1228139132.txt.gz · Zuletzt geändert: 2014-04-05 11:42 (Externe Bearbeitung)