PDAs & NPDAs ("Kellerautomat")

[Gast]

Eine Frage zu diesen verflixten Dingern:

Wenn ein PDA (deterministisch) in einen akzeptierenden Zustand kommt und noch Variablen auf den Stack lagern, kann das Wort dann akzeptiert werden? Oder muss der Stack leer sein?

Klartext:
Akzeptierender Zustand UND Stack leer
oder
Akzeptierender Zustand ODER Stack leer

Beispiel:

L = {a^n, b^m , 0 <= m <= n}

Eingabewort 'aab'



€(Epsilon), $ -> $ €, $ -> $
€, a -> a €, a -> a
-> q0 ----------------------> q1 -----------------------> q2(akzept.)

Schleife q0 Schleife q1
a, a -> aa b, a -> €
a, $ -> a$


Falls jemand durchsieht (die 'Zeichnung' oder im Allgemeinen) und Antwort weiss: Danke im Vorraus!

PS: Nein, Google und Wikipedia brachten bisher keine allzu klare Loesung.

[Gast]

Sorry aber kann nicht editieren und habe festgestellt das die Zeichnung Muell ist...
Hier Versuch #2:

Eingabewort 'aab'

...........€(Epsilon), $ -> $....................€, $ -> $
...........€, a -> a...............................€, a -> a
-> q0 ----------------------> q1 -----------------------> q2(akzept.)

..Schleife q0...................Schleife q1
..a, a -> aa....................b, a -> €
..a, $ -> a$

[MadMax@]

imho sind beide Aktzeptans bedinungen gleichwertig.

[Gast]

danke für die schnelle antwort :) dann ist das jetzt endlich klar.
dann ist ja der einzige Unterschied zwischen PDA und NPDA, dass der PDA mit einer Eingabe nur in einen Zustand A "springen" kann und der NPDA wahlweise in A oder B!?

[Unfug]

Der deterministische endet ja sobald er in einem Endzustand gekommen ist.

Der Unterschied zwischen deterministisch und nichtdeterministisch ist, dass der NPDA sämtliche Möglichkeiten durchprobiert im Gegensatz zum PDA, dessen Weg quasi vorgeschrieben ist (wie bei endlichen Automaten)

[ethrandil]

danke für die schnelle antwort :) dann ist das jetzt endlich klar.
dann ist ja der einzige Unterschied zwischen PDA und NPDA, dass der PDA mit einer Eingabe nur in einen Zustand A "springen" kann und der NPDA wahlweise in A oder B!?
Du meinst wohl das richtige.
Ein NPDA geht quasi immer 'den richtigen' Weg von mehreren, um das Wort zu akzeptieren. Ist halt ein releativ abstraktes Konzept ;).

- eth

[Unfug]

Du meinst wohl das richtige.
Ein NPDA geht quasi immer 'den richtigen' Weg von mehreren, um das Wort zu akzeptieren. Ist halt ein releativ abstraktes Konzept ;).

- eth


Ich stell mir das einfach als rekursive Funktion vor.
Jeder mögliche Weg erzeugt eine neue Instanz. Gibt eine Instanz ein "True" zurück, wird das Wort akzeptiert

[Gast]

Du meinst wohl das richtige.
Ein NPDA geht quasi immer 'den richtigen' Weg von mehreren, um das Wort zu akzeptieren. Ist halt ein releativ abstraktes Konzept ;).

- eth
angenommen ich habe ein word abba und nach dem einlesen von abb erreicht der pda den akzeptierenden zustand, dann ist das wort akzetiert obwohl es nicht komplett eingelesen ist?
mir ist auch nicht ganz klar, was denn den (N)PDA von nem DFA bzw. NFA unterscheidet, ist es nur der Stack?Wozu ist der Stack eigentlich gut?
Für mich ist (N)PDA nen Buch mit sieben Siegeln, genauso wie das pumping Lemma^^.

[Unfug]

angenommen ich habe ein word abba und nach dem einlesen von abb erreicht der pda den akzeptierenden zustand, dann ist das wort akzetiert obwohl es nicht komplett eingelesen ist?

Yeah, thats right

mir ist auch nicht ganz klar, was denn den (N)PDA von nem DFA bzw. NFA unterscheidet, ist es nur der Stack?Wozu ist der Stack eigentlich gut?
Für mich ist (N)PDA nen Buch mit sieben Siegeln, genauso wie das pumping Lemma^^.
Der Stack ist dein Speicher (oder bildlich dein Stück Papier).

# = (kellerbodensymbol)
Zustand = Schreiben
a wird gelesen ,# bisher im Keller = A wird auf Blatt geschrieben ([A][#])
b wird gelesen, A im Keller = B wird auf das Blatt geschrieben([A][ B ][#])
b wird gelesen , B im Keller, Zustand wird zu 'Löschen' = B wird vom Blatt ausradiert ([A][#])
a wird gelesen , A im Keller = A wird ausradiert. ([#])
# im Keller = Wort wird erkannt


edit: Pumping Lemma kommt sofort...
edit2: Weisst Du wie das Pumping Lemma für reguläre Sprachen funktioniert? (damit ich weiss wieviel ich aufschreiben muss)

[AlSvartr]

angenommen ich habe ein word abba und nach dem einlesen von abb erreicht der pda den akzeptierenden zustand, dann ist das wort akzetiert obwohl es nicht komplett eingelesen ist?
mir ist auch nicht ganz klar, was denn den (N)PDA von nem DFA bzw. NFA unterscheidet, ist es nur der Stack?Wozu ist der Stack eigentlich gut?
Für mich ist (N)PDA nen Buch mit sieben Siegeln, genauso wie das pumping Lemma^^.
Stell dir z.B. die Sprache L={a^nb^n | n element N} vor ... Du kannst mit einem DFA bzw. NFA nicht prüfen, ob ein Wort in dieser Sprache enthalten ist, mit einem PDA/NPDA hingegen geht das schon..das Pumping Lemma für reguläre Sprachen sagt, dass innerhalb eines FA immer ein Zykel existiert, das beliebig oft wiederholt werden kann, so dass das Wort weiterhin in der Sprache enthalten ist (das Wort wird eben an dieser Stelle "aufgepumpt") ... für kontextfreie Sprachen sagt das Pumping Lemma einfach ausgedrückt, dass es zwei solche "Pumpstellen" gibt...merke: Du kannst mit dem PL nicht nachweisen, dass eine Sprache kontextfrei bzw. regulär ist, sondern nur, dass sie es NICHT ist.

[Psylo]

So, habe mich jetzt mal registriert
@unfug
was passiert wenn kein kellerbodensymbol mehr da ist? dann hält der automat an oder? Wieso muss dieses Symbol da sein, damit der Automat weis wo schluss ist?
Was passiert mit Eingaben, die sich noch auf dem Stack befinden und der akzeptierte Zustand erreicht wurde?dann wurde es nicht erkannt richtig!?

Stell dir z.B. die Sprache L={a^nb^n | n element N} vor ... Du kannst mit einem DFA bzw. NFA nicht prüfen, ob ein Wort in dieser Sprache enthalten ist
Die Sprache sagt doch, dass ich ein Wort bilden muss, welches eine Anzahl an 'a' gefolgt von der gleichen Anzahl von 'b' hat. jetzt kann ich mir doch nen DFA bauen, der genau diese Wörter annimmt oder?

Zum PL
Ich habe hier eine Aufgabe + Lösung einer Probeklausur die ich nicht nachvollziehen kann und dummerweise verstehe ich meine eigenen Aufzeichnungen der Vorlesung auch nicht mehr :(

Beweisen Sie, dass die Sprache L={ 0^p 1^q | 0 <= q<= p} nicht regulär ist.
Beweis durch Widerspruch mit Hilfe des Pumping Lemmas.
Wir nehmen an, dass L5 regulär ist.
Sei m die Zahl von Pumping Lemma. // irgendeine natürliche Zahl oder?
Wir betrachten das Wort w = 0^m 1^m . Das Wort gehört der Sprache L5 und m <= |0^m 1^m |.
Laut Pumping- Lemma w = x y z, mit |xy| <= m. Daher sind xy und y in 0^m .
Laut Pumping Lemma ist y nicht leer. Sei k = |y| .
Laut Pumping Lemma ist auch x y^0 z ein Wort der Sprache L5.
Aber x y^0 z = 0^m-k 1^m, und m-k < m, ein Widerspruch mit der Sprache L5.
Wir haben ein Wort gefunden, das dem Pumping Lemma widerspricht. Daher ist die Annahme "die Sprache L5 wäre regulär" falsch.

ich kapiere immer nicht, wie jetzt das Wort, welches ja aus 2 Teilwörtern besteht in 3 Teile zerlegt wird, daran beiße ich mir die Zähne aus^^
m darf also nicht größer sein, als die Länge des Wortes richtig?

und weil das alles noch nicht genug ist, kommt jetzt noch eine Teilaufgabe

Geben Sie einen Kellerautomaten K an, der diese Sprache akzeptiert. Ist K deterministisch?
Im Anhang ist die Lösung.
a ==0 und b==1
Die Schreibweise ist denke ich so zu lesen (bei q0)
Wenn ein 'a' gelesen wird und ein 'Z' auf dem Stack liegt, dann ersetze Z durch aZ.
Wenn ein 'a' gelesen und ein 'a' auf dem Stack liegt, dann schreibe ein 'aa' auf den Stack.
Bei q0 bekomme ich schon Probleme. Wieso schreibe ich da 'aZ' bzw 'aa' drauf und nicht nur dieses eine gelesene Zeichen?

Ich hoffe, ihr seit nachsichtig mit meiner Unwissenheit und helft mir ein wenig weiter.
Werde leider erste gegen Sonntag wieder hier reinschauen können, deshalb wünsche ich schonmal nen schönes Wochenende.

MfG
Psylo

[AlSvartr]

So, habe mich jetzt mal registriert
Die Sprache sagt doch, dass ich ein Wort bilden muss, welches eine Anzahl an 'a' gefolgt von der gleichen Anzahl von 'b' hat. jetzt kann ich mir doch nen DFA bauen, der genau diese Wörter annimmt oder?

Nein, kannst du nicht. Du müsstest dir ja eine _beliebige_ Anzahl des Buchstaben a merken und genau so oft den Buchstaben b bekommen. Dafür benötigst du aber einen (unendlichen) Speicher, und den hat weder ein DFA noch ein NFA - im Gegenteil, du würdest hier unendlich viele Zustände benötigen - den erhältst du eben erst mit dem PDA.

Fürs Pumping Lemma hab ich dir mal drei Beispielklausuren rausgesucht, bei einer gehts um Kontextfreiheit, bei den anderen beiden um die Regularität. Vielleicht hilfts ja..

http://root.alsvartr.de/forum/3dc/TheorieIISS05Uebung7.pdf
http://root.alsvartr.de/forum/3dc/TheorieIWS04_05Uebung5MusterKlausurLoes.pdf
http://root.alsvartr.de/forum/3dc/TheorieIWS04_05Uebung6MusterKlausurLoes.pdf

[Unfug]

Ok immer der Reihe nach.

Pumping Lemma für reguläre Sprachen:
Zunächst einmal brauchen wir deren Vorraussetzung:

1) |v| >= 1
2) |uv| <= n
3) für i aus N gilt uv^i w ist aus L

Nehmen wir jetzt mal das Beispiel a^n b^n .
Du kannst Dir merken, alles wozu man einen Counter bräuchte, ist NICHT REGULÄR. Aber wir beweisen es mittels Pumping Lemma:

Die IDEE:
Du hast eine Sprache, mit bestimmten Anzahl von Zuständen. Sagen wir 3. Wenn Dein Wort nun aber länger als 3 Zeichen ist, dann durchläuft es mindestens einen Zustand mehrmals.
Klingt kompliziert ist es aber gar nicht. Nehmen wir das Wort aaaabbbb.
Hier wirst Du einen Zustand (Kreis) haben, der immer wieder durchlaufen wird. Und zwar 4x den Zustand a und 4x Zustand b. Also wie auf deinem Bild bei q0 und q1. (Eine Pfeil in sich selbst).
Also zurück zu unserem Wort: Da es also länger ist als Zustände vorhanden, ist 1) gültig, weil v unsere 'Schleife' darstellt. Und Da Du sie ja durchäufst ist diese nunmal mindestens >=1.

Die zweite Idee ist uv <= n
Unser zuvor gewähltes Wort (aaaabbbb) ist länger als 3 (n = 3, n = die Anzahl der Zustände).
Wenn Du jetzt bis zur Schleife die Anzahl Zustände zählst, dann könnten es ja "maximal" n sein. Weil mehr stehen ja nicht zur Verfügung
Also ist 2) gültig. Das ist eigentlich immer so. Ist halt nur "Theorie;-)".

So wir sind jetzt also an der Schleife v .
Wenn wir diese jetzt durchlaufen durchlaufen durchlaufen u..s.w und zwar sagen wir 10000000Millionen mal. Dann hätten wir folgendes Wort a.......abbbb.
Wir hätten also Millionen von a´s aber nur 4 b´s.
Diese Art von Wörtern sind aber nicht in der Sprache erlaubt (a´s und b´s müssen gleichviele sein).
3) ist nicht gültig.
Und da eine nicht gültige Bedingung von den drei ausreicht um zu zeigen (und es immer die 3) bedingung ), daß das Wort nicht zur Sprache gehört. Hast Du nun bewiesen, daß das Wort nicht zu L gehört.

Verstanden?


edit:was passiert wenn kein kellerbodensymbol mehr da ist? dann hält der automat an oder? Wieso muss dieses Symbol da sein, damit der Automat weis wo schluss ist?
Was passiert mit Eingaben, die sich noch auf dem Stack befinden und der akzeptierte Zustand erreicht wurde?dann wurde es nicht erkannt richtig!?
Das Kellersymbol ist immer da. Das ist der "BODEN", "der Grund" ,"der Fußboden". Wie man es sehen will. Ein Stack ist wie so ein Wäschekorb. Du tust Wäsche rein und raus. Aber du hast immer noch einen Boden (nämlich vom Wäschekorb).
Sobald das Bodensymbol gelesen wird und das Wort akzeptiert wurde, dann ist Ende. Was mit dem Rest passiert ist scheiss egal. Das bleibt drauf oder der Stack verschwindet oder bleibt im Speicher oder wird an die Blumenfrau nebenan verschickt.

[MadMax@]

Wie unendlich froh ich bin das ich alle Prüfungen über Theo geschrieben habe.

PS:Komplexitätstheorie war abartig:-)

[Psylo]

so, lange nix mehr von mir hören lassen.
also letzte woche donnerstag war klausur in dem fach. die aufgaben, wo pda und pl drankamen habe ich zeitlich nicht mehr wirklich schaffen können.
insgesamt habe ich ne 3,3 geschrieben.eigentlich schlecht aber eigentlich bin ich froh, dass ich das fach nun nach dem 2. mal belegen endlich los bin :)

danke für eure hilfe.
mfg
Psylo