Determinismus

ein Automat A = (Σ, Q, I, F, δ) heißt deterministisch, wenn

• | I| = 1
• und zu jedem (p, w, q)∈Q×Σ^*×Q höchstens ein
  mit w markierter Pfad von p nach q in A existiert.

zu jedem Automaten gibt es einen sprach-äquivalenten deterministischen.

nicht deterministische Automaten sind trotzdem nützlich:

• kleiner oder besser lesbar (Bsp: Automat für Σ^*abaΣ^*)
• effiziente Beschreibung mehrerer Möglichkeiten,
• Beschreibung nicht vorhersehbarer (Benutzer-)Aktionen.