Deteministische Automaten

Id: det.tex,v 1.2 2004/12/14 12:36:40 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).