Deteministische Automaten

Id: det.tex,v 1.1 2007-10-31 17:50:50 waldmann Exp

• A heißt vollständig, wenn es zu jedem (p, c) wenigstens ein q mit p$\;\stackrel{{c}}{{\to}}\;$_Aq gibt.
• A heißt deterministisch, falls
  • die Start-Menge S(A) genau ein Element enthält und
  • die Relation T(A) sogar eine partielle Funktion ist (d. h. zu jedem (p, c) gibt es höchstens ein q mit p$\;\stackrel{{c}}{{\to}}\;$_Aq.
  Dann gibt es in A für jedes Wort w höchstens einen mit w beschrifteten Pfad vom Startzustand aus.

Satz: Zu jedem Automaten A gibt es einen deterministischen und vollständigen Automaten D mit L(A) = L(D).