Theoretische und technische Informatik - ganz praktisch
Herzlich willkommen auf der Question/Answer-Plattform zu Grundlagen der Informatik II. Wir wünschen Ihnen viel Spaß beim Lernen und Diskutieren!
Loggen Sie sich mit Ihrem KIT-Account (u...) ein, um loszulegen!
Beachten Sie auch diese Informationen zum Schnelleinstieg.
(Nicht-KIT-Studierende beachten bitte diese Informationen.)

Schöne Ferien!
 

 

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

+1 Punkt
156 Aufrufe

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

 

Gefragt 29, Sep 2015 in 2011-B-02 von uafjv uafjv Tutor(in) (167,990 Punkte)  

Eine Antwort

0 Punkte

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)

 

Beantwortet 29, Sep 2015 von uafjv uafjv Tutor(in) (167,990 Punkte)  
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)
Darf ich in den Keller was anderes schreiben, als ich lese?
...