Deterministischen pushdown automat

06.01.2014, 13:24

marie m

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?

06.01.2014, 15:59

Auf diesen Beitrag antworten »

Karlito

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

08.01.2014, 15:26

Auf diesen Beitrag antworten »

marie m

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}?

08.01.2014, 22:18

Auf diesen Beitrag antworten »

Karlito

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.

12.01.2014, 01:55

Auf diesen Beitrag antworten »

marie m

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

13.01.2014, 23:35

Auf diesen Beitrag antworten »

Karlito

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

14.01.2014, 02:48

Auf diesen Beitrag antworten »

marie m

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?

14.01.2014, 07:40

Auf diesen Beitrag antworten »

Karlito

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

14.01.2014, 10:51

Auf diesen Beitrag antworten »

marie m

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?

14.01.2014, 11:11

Auf diesen Beitrag antworten »

Karlito

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

14.01.2014, 13:42

Auf diesen Beitrag antworten »

marie m

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?

14.01.2014, 20:06

Auf diesen Beitrag antworten »

Karlito

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

14.01.2014, 22:25

Auf diesen Beitrag antworten »

marie m

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

15.01.2014, 16:31

Auf diesen Beitrag antworten »

Karlito

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

25.01.2014, 01:35

Auf diesen Beitrag antworten »

marie m

Vielen Dank für deine Hilfe!!!

Neue Frage »

Antworten »

Deterministischen pushdown automat

Verwandte Themen