Notizen

Deterministischer Endlicher Automat

tagstheoretische_informatik, formale_sprachtheorie
aliasesDEA

Ein deterministischer endlicher Automat (kurz DEA) ist ein 5-Tupel , wobei:

  • ist eine endliche Zustandsmenge
  • ist ein endliches Alphabet
  • ist die Übergangsfunktion
    • Signatur:
  • ist der Startzustand
  • die Menge der akzeptierten Endzustände

Siehe auch

Akzeptanz

Sei die Eingabe mit und . Ein DEA akzeptiert die Eingabe , wenn eine Sequenz aus Zuständen aus existiert, die folgende Bedingungen erfüllt:

  • für

Alternative Definition Akzeptanz

Induktive Fortsetzung von auf :

  • Für

Akzeptierte Sprache eines DEA

Misplaced &L(M) & = \{w_1 w_2 \dots w_n | \hat{\delta}(q_0, w_1 w_2 \dots w_n) \in F\} \\ & = \{w | \hat{\delta}(q_0, w) \in F\} \end{align}

Terminologie

  • Ein Automat akzeptiert eines oder mehrere bestimmte Wörter
  • Ein Automat erkennt genau eine Sprache

Wissenswert

Für Endzustände wird meist das Präfix verwendet, “Trap-Zustand”:

Backlinks