Übungsblatt 11 Aufgabe 4 c)

Hier könnt ihr euch über die Inhalte der Übungsblätter austauschen und Fragen stellen.

Übungsblatt 11 Aufgabe 4 c)

Beitragvon s9cimich » 09 Feb 2014, 19:40

Ich hab mal eine Frage zu Blatt 11 Aufgabe 11.4 c)
Da soll zu einem PDA_Q^K P ein aequivalenter PDA P' angeben werden, also die Zustaende entfernen.
Angenommen es gibt Woerter x und y, die P durch leeren Stack akzeptiert, indem er im Startzustand s anfaengt und sodass er fuer x in s und fuer y in q endet.
Jetzt muss P' aber einen Startstackzustand aus Q x Gamma x Q haben. Ich glaube nicht, dass man den allgemein angeben kann.
Klar ist dass es entweder s bottom s oder s bottom q sein soll, da wir in s anfangen moechten und dann in irgendeinem Zustand enden muessen.
Aber wenn wir uns fuer s bottom s entscheiden, kann y nicht erkannt werden; fuer die andere Wahl x nicht.
(P' will be able to scan a string x starting with only <p A q> on its stack and end up with an empty stack
iff P can scan x starting in state p with only A on its stack and end up in state q with an empty stack. S. 173, Kozen)
Kozen umgeht das ganze indem er sagt, dass wir in genau einem finalen Zustand den Stack leeren.

D.h. man kann ohne P genauer zu analysieren gar keinen Startstackzustand angeben und so auch keinen aequivalenten PDA erhalten.
Ergibt das Sinn, was ich rede? :)
s9cimich
 
Beiträge: 1
Registriert: 06 Dez 2013, 18:38

Re: Übungsblatt 11 Aufgabe 4 c)

Beitragvon Marc.Roth » 10 Feb 2014, 19:13

Hallo,

ja, für die im Buch angegebene Konstruktion muss für den PDA gelten, dass er nach einer akzeptierenden Berechnung einen leeren Keller hat und in sich in einem eindeutigen Endzustand befindet.

Wenn nun ein PDA_Q^K gegeben ist, kann dieser mit der bekannten Konstruktion in einen PDA umgewandelt werden, der die obigen Anforderungen erfüllt.
(Nachdem der Keller leer ist gehen wir in einen eindeutigen Endzustand.)

Dann kann die Konstruktion aus dem Buch angewendet werden.
(Dieses Vorgehen funktioniert dann auch ohne den PDA_Q^K genauer zu analysieren.)

Ich hoffe, das beantwortet deine Frage :)

VG
Marc
Marc.Roth
 
Beiträge: 1
Registriert: 16 Okt 2013, 12:58


Zurück zu Übungsblätter

Wer ist online?

Mitglieder in diesem Forum: 0 Mitglieder und 0 Gäste

cron