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!
 

 

Bonusklausur 2013

0 Punkte
64 Aufrufe

​Hallo,

ich habe ein Frage: Ich habe folgenden Kellerauromaten geschrieben(s.u):

Wieso akezptier der  KA das Beispielwort nicht? Er müsste doch wenn er das letzte a gelesen hat, als nachdem er (s3, a, k) => (s3,k) ausgeführt hat, als letztes den Übergang (s3, lamda, k) => (se, k) ausführen und stehen bleiben und das Wort akzeptieren.

 

hier c = #

pda:
(s0, a, k) => (s1, ak);
(s1, b,a) => (s1, ba);
(s1, a,a) =>(s1, aa);
(s1, a,b) =>(s1, ab);
(s1, c,a) => (s2, a);
(s2, a,a) => (s2, lambda);
(s2, a,b) => (s2, b);
(s2, b,b) => (s2,lambda);
(s2, a,k) => (s3, k);
(s3, a,k) => (s3, k);
(s3, lamda,k) => (se, k)
--declarations--
s0=s0;
F=se;
kSymb=k;
inputs=aabaacaaabaaaa
--declarations-end--
 
Vielen Dank!

 

Gefragt 12, Jan 2017 in 2013-B-01 von Anonym  
Das liegt daran, dass Sie "lambda" falsch geschrieben haben :-)
Danke.... :( :DD
Ist der Automat wegen
 (s3, a,k) => (s3, k);
(s3, lamda,k) => (se, k);
dann nichtdeterministisch ?
Ganz genau. Nicht jedes $\lambda$ auf der linken Seite führt allerdings dazu, dass der Automat nichtdeterministisch wird. Es hängt immer davon ab, ob es sein kann, dass der Automat "vor der Wahl steht", eine von mehreren Möglichkeiten zu verfolgen. Im obigen Fall wüsste ein deterministischer KA nicht, ob er auf dem Eingabezeichen $a$ bei Lesen des Kellersymbols $k$ den ersten oder den zweiten Übergang nutzen soll.

Ihre Antwort

Ihr anzuzeigender Name (optional):
Datenschutzhinweis: Ihre E-Mail-Adresse wird ausschließlich benutzt, um Ihnen Benachrichtigungen zu schicken. Es gilt die Datenschutzerklärung.
Anti-Spam-Abfrage (Captcha):
Bitte loggen Sie ein oder registrieren sich, um diese Abfrage (Captcha) zu vermeiden.
...