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.)

Kellerautomat unvollständig?

+1 Punkt
93 Aufrufe

Fehlt hier nicht das leere wort?

 
(s0, b, k) => (s0, ak);
(s0, a, k) => (s0, ak);
(s0, b, a) => (s0, aa);
(s0, a, a) => (s0, aa);
(s0, d, a) => (s1, lambda);
(s0, c, a) => (s1, lambda);
(s1, d, a) => (s1, lambda);
(s1, c, a) => (s1, lambda);
 
(s1, lambda, a) => (se,k);
(s1, lambda, k) => (se,k);
Gefragt 18, Jan 2016 in SAA-1-2 von uagll uagll Lernwillige(r) (1,100 Punkte)  

Eine Antwort

0 Punkte
Hallo uagll,

es ist in dieser Aufgabe kein extra Zustand Se definiert. Außerdem wäre der Automat mit dem Übergang (s1, lambda, a) nicht mehr deterministisch, da für den Zustand s1 und das Kellerzeichen a bereits ein Übergang definiert ist. Der Übergang in den Enzustand mit dem leeren Wort ist aber auch nicht notwendig, weil s0 und s1 beides Endzustände sind. Das Wort wird also akzeptiert, sobald es der Automat abgearbeitet hat.

Viele Grüße

Gregor (Tutor)
Beantwortet 18, Jan 2016 von uhdzw uhdzw Tutor(in) (102,490 Punkte)  
Hallo,
und wenn s1 der Endzustand ist und wir z.b. aaccd(was nicht akzeptiert werden muss) eingeben, dann stoppt der Kellerautomat in s1 (was ein Endzustand ist). Und dadurch, dass nicht das ganze Wort abgearbeitet ist, kommen wir zum Schluss, dass das Wort nicht akzeptabel ist.
Also allein Endzustand bringt nichts. Verstehe ich das richtig?
Danke und Gruss
Das würde mich auch noch interessieren, also ob zum Annehmen des Wortes nicht nur erforderlich ist, dass der Automat sich im Endzustand befindet sondern auch, dass das Wort vollständig abgearbeitet wurde?
Genau so ist es.
...