Nichtdeterministische Endliche Automaten

Endlichen Automaten wechseln ihren Zustand in Abhängigkeit vom eingelesenen Zeichen. Im Gegensatz zu Deterministischen Endlichen Automaten (DEA) kann man bei Nichtdeterministischen Endlichen Automaten (NEA) mehrere mögliche Zielzustände festlegen. Durch die Einführung von Übergängen, bei denen gar kein Zeichen gelesen wird (ε-Übergänge), lässt sich das Maschinenmodell zu ε-NEA ausweiten. Allerdings sind alle drei Maschinenmodelle DEA, NEA und ε-NEA gleich mächtig: Mit ihnen kann man die gleichen Entscheidungsprobleme lösen.

0:00 von Automaten akzeptierte Sprache
2:40 Beispiel für NEA
5:08 Definition NEA
6:45 NEA akzeptiert Strings
8:48 NEA schaut in die Zukunft
11:30 DEA speichert die Vergangenheit
15:53 NEA in DEA umwandeln
24:29 ε-Übergänge
26:06 Definition ε-NEA
27:19 ε-NEA akzeptiert Strings
30:47 Beispiel für ε-NEA
32:25 unendlich lange Pfade?
34:04 ε-NEA in DEA umwandeln
39:57 Fazit: DEA = NEA = ε-NEA