Fuer einen Automaten A = mit |Q|= k gibt es fuer jedes Paar (q,a) genau k+1 Moeglichkeiten fuer seinen Wert unter d, naemlich entweder jeden der k Zustaende oder aber gar keinen der Zustaende. Wenn fuer d der letzte Fall fuer kein (q,a) auftritt, ist d bereits total. Wenn d auch nur fuer ein Paar (q,a) nicht definiert ist, ist es eine partielle Funktion. Wenn man nun unbedingt eine totale Funktion haben will, kann man einen Automaten A% = betrachten, bei dem d' wie folgt definiert ist: d'(q,a) = d(q,a), falls d(q,a) definiert d'(q,a) = % , falls d(q,a) nicht definiert sowie d'(%,a) = % fuer alle a in Sig Die Idee heisst nach Scott "Objektifizierung des Undefinierten", d.h. das Undefinierte wird als neuer Wert (hier also Zustand) dazugenommen. Die Prozedur nennt man "lifting", vermutlich weil der bisherige Zielbereich der Funktion ueber ein neues, gewissermassen minder- wertiges Element angehoben wird. Natuerlich kann man diese Konstruktion auch anwenden, wenn d schon total war. Man hat dann einfach einen Zustand mehr, der einfach nicht erreicht wird, weswegen man ihn auch gleich wieder entfernen kann. Bei der Konstruktion eines DEA A^ aus einem NDEA A = erhaelt man als Zustandsmenge Q^ die Potenzmenge P(Q) der alten Zustandsmenge. Und ein Element von P(Q) ist natuerlich die leere Menge. Gleichzeitig ist aber d^(q^,a) = Vereinigung ueber alle q in q^ von d(q,a); fuer alle a ist dann aber d^({},a) = {}. Das bedeutet also, dass zwar Uebergaenge in {} hineinfuehren koennen, aber danach gibt es kein Entkommen mehr. Damit hat {} in der Konstruktion eines DEA aus einem NDEA genau die Rolle von %. Allerdings kann es sein, dass sich durch die Konstruktion kein Uebergang nach {} von einem anderen Zustand als {} selbst aus ergibt. Dann kann man im Zuge der Minimierung {} wieder wegfallen lassen, genau wie man sich oben bei einem totalen DEA A durch Hinzunehmen von % nur einen unerrechbaren Zustand einhandelt, den man folglich gleich wieder entfernen kann. Soweit zum Zusammenhang von Totalitaet, Partialitaet, % und {}. Michael Arndt