Bonusklausur 2013

Question

​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!

 

Comments

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.