hallo hans

habe mir gerade deine löung angeschaut zur aufgabe 2 vom blatt 5
(komma-zahelen-automat) (endlicherAutomat.pdf)  und verstehe nicht 
warum der 3. automat deterministisch sein soll (zumindest annähernd).
warscheinlich gehöre ich zu denen die es "ganz genau" nehmen, aber für
mich ist der genauso (nicht)deterministisch wie der 1. automat aus der 
vorlesung weil wir die optionen haben führende null oder nicht, und ganze 
zahl ohne komma, kann man diesen automaten (so wie ich das verstanden habe) 
nicht terministisch machen. oder irre ich mich? vielleicht könntest du mir 
(oder allen, in dem du die lösung erweiterst) erklären warum der 3. automat 
deterministischer ist als der 1. aus der vorlesung.

Antwort:
Der Unterschied zwischen einem deterministischen und einem
nichtdeterministischen Automaten besteht darin, daß bei
einem determ. Automaten alle Übergänge eindeutige definiert
sind. Der Begriff Determinismus bezieht sich also auf die
Zustände und deren Übergänge und nicht auf die Wörter, die
von dem Automaten erzeugt werden!

Hierzu ein Beispiel:
Bei Automat 1 gibt es 2 Möglichkeiten, ausgehend von Zustand S
eine Ziffer zu erzeugen: Zum einen von Zustand S nach
S selber und von Zusatnd S nach Zustand E.
Nichtdeterminismus bedeutet hier also, daß es nicht eindeutig,
ist, welcher Weg von S aus genommen werden muß, wenn eine Ziffer
erzeugt werden soll!

Beispiel zum 3. Automat:
Möchte man ausgehend vom Startzustand ein a, eine 0 oder
einen . erzeugen, so gibt es immer genau 1 Möglichkeit.
Der Weg um z.B. die 0 vom Startzustand aus zu erzeugen
ist also deterministsch, nämlich immer von S nach E1!

Was bedeutet die Bemerkung zu Automat 3:
Betrachten wir bei Automat 3 Zustand X: Von X geht genau
1 "a" Weg und genau 1 "z" Weg ab. Also kann man von
Determinismus sprechen. Allerdings: Wenn wir die Mengen
a und z auflösen gibt es von Zustand X aus gesehen
2 Möglichkeiten um z.B. die 1 zu erzeugen...

Letzte Anmerkung:
Theoretisch sind nichtdet. und det. Automaten
äquivalent. D.h. auch Automat 3 kann in einen
wirklichen deterministischen Automaten überführt
werden! Aber hierzu müßte man die Potenzmenge
aller Zustände bilden, was den Rahmen dieser
Übung sprengen würde...