Informatiker Board | Druckvorschau: Deterministischen pushdown automat

Informatiker Board (http://www.informatikerboard.de/board/index.php)
- Themengebiete (http://www.informatikerboard.de/board/board.php?boardid=1)
--- Theoretische Informatik (http://www.informatikerboard.de/board/board.php?boardid=5)
---- Automatentheorie (http://www.informatikerboard.de/board/board.php?boardid=13)
----- Deterministischen pushdown automat (http://www.informatikerboard.de/board/thread.php?threadid=1765)

Geschrieben von marie m am 06.01.2014 um 13:24:

Deterministischen pushdown automat

Hallo!!

Ich muss zeigen dass die Sprache L={w in {a,b}*: w=a^i b^j, i != j} von einen deterministischen pushdown automat akzeptiert wird.

Könnt ihr mir sagen wie man deterministische pushdown automaten macht? Oder muss ich einfach zeigen dass die Sprache kontextfrei ist?

Geschrieben von Karlito am 06.01.2014 um 15:59:

Hallo,

in der Regel reicht es eigentlich eine Beschreibung anzufertigen, wie dieser Pushdown- oder Kellerautomat funktionieren soll. Schlimmstenfalls musst Du ihn formal angeben.

Die Funktionsweise wäre in diesem Fall:
- Für jedes gelesene a: lege ein A auf den Kellerspeicher (Stack)
- Anschließend: für jedes gelesene b, entferne ein A vom Kellerspeicher
- Ist der Stack leer, gehe in den akzeptierenden Zustand über (es können weitere b gelesen werden)

Nichtakzeptanzfälle:
- Es wir ein b zuerst gelesen
- Es wird nach einem b ein a gelesen
- Es befinden sich noch Zeichen auf dem Stack

Ich hoffe das ist verständlich, sonst gern nachfragen.

VG,

Karlito

Geschrieben von marie m am 08.01.2014 um 15:26:

Muss ich also was ähnliches machen wie in dieser Seite http://de.m.wikipedia.org/wiki/Kellerautomat (>Formale Definition) beim Beispiel über die kontextfrei Sprache L={a^n b^n|n>=0}?

Geschrieben von Karlito am 08.01.2014 um 22:18:

Ja genau. Man sollte das auch mal gemacht haben.

Ich habe den Automaten übrigens nciht ganz richtig beschrieben. Ich weiß nicht warum, aber ich habe den Automaten für i>=j und nicht i!=j beschrieben... Du müsstest den Automaten entsprechend anpassen.

Geschrieben von marie m am 12.01.2014 um 01:55:

Ich habe versucht die Beschreibung zu machen...

Erste habe ich die Grammatik geschrieben:
$[latex] S \to AB|CD [/latex]$
$[latex] A \to aAb|\varnothing [/latex]$
$[latex] B \to bB|b [/latex]$
$[latex] C \to aC|a [/latex]$
$[latex] D \to aDb|\varnothing [/latex]$

Die Beschreibung ist die Folgende:
$[latex] (p, \varepsilon , \varepsilon ), (q, S) [/latex]$
$[latex] (q, \varepsilon , S), (q, AB) [/latex]$
$[latex] (q, \varepsilon , S), (q, CD) [/latex]$
$[latex] (q, \varepsilon , A), (q, aAb) [/latex]$
$[latex] (q, \varepsilon , A), (q, \varepsilon ) [/latex]$
$[latex] (q, \varepsilon , B), (q, bB) [/latex]$
$[latex] (q, \varepsilon , B), (q, b) [/latex]$
$[latex] (q, \varepsilon , C), (q, aC) [/latex]$
$[latex] (q, \varepsilon , C), (q, a) [/latex]$
$[latex] (q, \varepsilon , D), (q, aDb) [/latex]$
$[latex] (q, \varepsilon , D), (q, \varepsilon ) [/latex]$
$[latex] (q, a, a), (q, \varepsilon ) [/latex]$
$[latex] (q, b, b), (q, \varepsilon ) [/latex]$

Ist das richtig?? verwirrt

Geschrieben von Karlito am 13.01.2014 um 23:35:

Hallo Marie,

das ist leider nicht richtig:
1. Produktionen können nie die leere Menge erzeugen. Das leere Wort an dieser Stelle macht die Grammatik korrekt.
2. Du benutzt den Keller falsch. Symbole können nur auf den Kellerspeicher gelegt werden oder von oberster Stelle von diesem entnommen werden.

Soweit ich weiß existieren Verfahren, um aus Grammatiken Kellerautomaten zu konstruieren. Ich habe davon aber keins erlernt. Ich finde es an dieser Stelle einfacher den Automaten ohne eine zugrundeliegende Grammatik zu erstellen. Dazu wäre es erst einmal günstig, wenn Du beschreibst, wie der Automat funktionieren soll.

VG,

Karlito

Geschrieben von marie m am 14.01.2014 um 02:48:

Zitat:

Original von Karlito

- Ist der Stack leer, gehe in den akzeptierenden Zustand über (es können weitere b gelesen werden)

Kann es aber so nicht vorkommen dass die Anzahl der gelesene a's gleich ist mit der Anzahl von b, das aber nicht erlaubt ist?

Geschrieben von Karlito am 14.01.2014 um 07:40:

Richtig!

Zitat:

Original von Karlito
Ich habe den Automaten übrigens nciht ganz richtig beschrieben. Ich weiß nicht warum, aber ich habe den Automaten für i>=j und nicht i!=j beschrieben... Du müsstest den Automaten entsprechend anpassen.

...

VG,

Karlito

Geschrieben von marie m am 14.01.2014 um 10:51:

Zitat:

Original von Karlito
Richtig!

Zitat:

...

VG,

Karlito

Also ist die Funktionsweise in diesem Fall:
- Für jedes gelesene a: lege ein A auf den Kellerspeicher (Stack)
- Anschließend: für jedes gelesene b, entferne ein A vom Kellerspeicher
- Ist der Stack leer, gehe in den akzeptierenden Zustand über,es müssen aber witere b gelesen werden ?

Aber,wenn es so wäre müsste der Automat mehr bs als as lesen,das muss aber nicht so sein...Es könnte nämlich auch mehr as als bs lesen..Was könnte ich ändern?

Geschrieben von Karlito am 14.01.2014 um 11:11:

Hallo,

im Normalfall sollte ja ein Kellerstartsymbol initial auf dem Keller liegen. Nun muss sich ja nur die Anzahl der gelesenen a und die Anzahl der gelesenen b unterscheiden. Wenn das Kellerstartsymbol auf dem Keller liegt, sollte also das Wort gerade nicht akzeptiert werden. D.h. das ist der Fehlerfall.

Weiterhin muss geprüft werden, dass auf ein b nicht wieder ein a folgt -> Fehlerzustand...

VG,

Karlito

Geschrieben von marie m am 14.01.2014 um 13:42:

Also wenn der Keller leer ist, sollte das Wort gerade nicht akzeptiert werden? Muss aber nicht der Keller immer zum Schluss leer sein? Oder habe ich es falsch verstanden?

Geschrieben von Karlito am 14.01.2014 um 20:06:

Hallo,

es gibt zwei Definitionen von PDAs. Eine davon ist tatsächlich so, dass es keine FInalzustände gibt und der PDA die Eingabe akzeptiert, sobald der Stack leer ist.
Für diese Art des PDA müsstest Du einfach, wenn das Ende der Eingabe erreicht ist (nach dem letzten b) solange den Stack bearbeiten, bis er leer ist.

VG,

Karlito

Geschrieben von marie m am 14.01.2014 um 22:25:

Damit ich das besser verstehe könntest du mir die Funktionsweise des Kellerautomaten beschreiben?

Geschrieben von Karlito am 15.01.2014 um 16:31:

Hallo,

ja. Siehe Anhang. Ich hoffe ich habe keine Fehler gemacht.

Im Prinzip ist es so, dass der Keller eben immer leer geräumt werden muss. Zum Beispiel wird das Wort aa Akzeptiert. Damit man bestimmen kann, dass die Anzahl an "a" und die Anzahl an "b" verschieden sind, muss man "zählen". Dazu werden Elemente auf den Kellerspeicher gelegt. In meinem Fall das Kellersymbol "A".

Legende zu meinem Beispiel:
qf ... FInalzustand (final)
qe ... Fehlerzustand (error)
qc ... Zustand zu Leeren des Kellers (clean)
q1 ... Initialzustand
q2 ... Zustand zu Lesen von "a"
q3 ... Zustand zu Lesen von "b"
q4 ... Zustand zu Lesen von "b" nachdem die Anzahl vin "b" = Anzahl von "a"
* ... Beliebiges Zeichen
# ... Kellerstartsymbol

VG,

Karlito