Könnte man nicht bei den ersten beiden Übergängen in s0 bleiben?

Question

Hallo,

muss ich bei den ersten beiden Übergängen in den Zustand s1 wechseln?

Könnte nicht in s0 bleiben?

Dazu würde ich die Übergänge s1 zunächst alle in s0 umbenennen.

Danke im Voraus

 

Answer 1

Hallo,

in diesem Fall muss man in den Zustand s1 wechseln, da das leere Wort Teil der Sprache ist und anderenfalls dein Automat nicht deterministisch wäre! (Denn dann dürfte s0 kein Endzustand sein und du bäruchtest einen lambda Übergang der Form (s0,lambda,k0), womit dein Automat nicht mehr deterministisch ist!)

Gruß,

Adam (Tutor)

 

Comments

Aber wenn man doch den "(s0,lambda,k0)" Fall hat, dann ist der Automat doch deterministisch?

Denn dann kann man doch auch in s0 aufhören, wenn kein Wort eingegeben wird, oder?

Wann ist denn ein Automat genau deterministisch & wann nicht?

Bin gerade etwas verwirrt.

---

Hallo,

Ein KA ist nicht deterministisch, wenn es zwei Übergänge gibt, die der Automat zur selben Zeit ausführen könnte. Einfaches Beispiel:

(s0,a,k0)->(s0,ak0)

(s0,a,k0)->(s0,bk0)

Lese ich also am anfang ein a, dann erfülle ich die Voraussetzung für beide Übergänge und weiss nicht, welche ich ausführen soll (d.h. die Definition der Erkennung bei ndet. KA: Wenn es eine Folge von Überführungen gibt, sodass es akzeptiert wird, dann ist es Teil der Sprache).

Schauen wir uns jetzt speziell das mit dem lambda übergang an. Wir hätten also

(s0,lambda,k0)->(se,k0)

(s0,a,k0)->(s0,ak0).

Dies ist beides ausführbar, wenn mein Wort mit einem a beginnt! Denn das lambda dort heißt nicht, dass dieser Übergang verwendet werden darf, wenn kein Buchstabe gelesen wird, also das Band leer ist. Ein lambda Übergang darf immer gemacht werden, wenn Zustand und Kellerzeichen übereinstimmen.

Würde also ein a gelesen werden, dürfte ich trotzdem einen lambda-Übergang machen! Und genau so geht der Determinismus verloren und deshalb muss auch der Anfagnszustand ein Endzustand sein, wenn das leere Wort Teil der Sprache ist. Denn die einzige Alternative ist der lambda Übergang, den haben wir aber gerade augeschlossen.
Gruß, Adam (Tutor)