Notizen

Nichtdeterministischer Endlicher Automat

tagstheoretische_informatik, formale_sprachtheorie
aliasesNEA

Ein nichtdeterministischer endlicher Automat NEA ist ein 5-Tupel , wobei:

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

Siehe auch

Unterschied zum DEA

  • Mehrere alternative Übergänge mit gleichem Symbol sind möglich
  • Mehrere Startzustände sind möglich

Erweiterung: -NEA

  • Modifikation:
  • “Leere” Übergänge möglich

Transitionsfunktion

  • Übergang:
  • Zustand auf Menge von Zuständen abgebildet
  • Verallgemeinerung auf mittels
Misplaced & \hat{\delta}(Q', \epsilon) & = Q' \text{ für alle } Q' \subseteq Q \\ \\ \hat{\delta}(Q', w_1 w_2 \dots w_n) & = \bigcup_{q \in Q'} \hat{\delta}(\delta(q, w_1), w_2 \dots w_n) \end{align}$$

Definition: Akzeptierte Sprache eines NEA

Backlinks