Aliases:: endliche Automaten, Endliche Automaten, endlicher Automat
links::
reguläre Sprache
ToC
DEAs und formale Sprachen
NEAs
Automatenminimierung, Ă„quivalenzklassenautomat
Potenzmengenkonstruktion: NEA -> DEA
ϵ\epsilonϵ-Abschluss
[[Satz von Nerode]]
Nerode-Relation
content
def EA akzeptiert ein Wort sr
  ⟺  \iff⟺ er hält in einem akzeptierendem Zustand
def EA heiĂźt endlich, da sr
da Zustandsmenge endlich
(vgl. mit Speicher)
def zwei EA, heißen äquivalent sr
  ⟺  \iff⟺ akzeptieren dieselbe Sprache
Satz Ă„quivalenz von NEAs und DEAs sr
Zu jedem NEA gibt’s einen äquivalenten DEA.
Proof - Potenzmengenkonstruktion
Sprache ist regulär :⇒:\Rightarrow:⇒ EA konstruieren
Endliche Automaten
def/concept ein (D)EA besteht aus: sr
EA
reguläre Sprache -> [EA]
Im Automatenbereich :≅:\cong:≅ EA akzeptiert nie (bzw. kein Wort)