Deterministischen pushdown automat |
marie m
Eroberer
Dabei seit: 08.06.2013
Beiträge: 57
|
|
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 13:24 |
|
|
Karlito
Kaiser
Dabei seit: 11.04.2011
Beiträge: 1.461
|
|
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
|
|
06.01.2014 15:59 |
|
|
Karlito
Kaiser
Dabei seit: 11.04.2011
Beiträge: 1.461
|
|
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.
|
|
08.01.2014 22:18 |
|
|
marie m
Eroberer
Dabei seit: 08.06.2013
Beiträge: 57
|
|
Ich habe versucht die Beschreibung zu machen...
Erste habe ich die Grammatik geschrieben:
Die Beschreibung ist die Folgende:
Ist das richtig??
|
|
12.01.2014 01:55 |
|
|
Karlito
Kaiser
Dabei seit: 11.04.2011
Beiträge: 1.461
|
|
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
|
|
13.01.2014 23:35 |
|
|
marie m
Eroberer
Dabei seit: 08.06.2013
Beiträge: 57
|
|
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 02:48 |
|
|
Karlito
Kaiser
Dabei seit: 11.04.2011
Beiträge: 1.461
|
|
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 07:40 |
|
|
Karlito
Kaiser
Dabei seit: 11.04.2011
Beiträge: 1.461
|
|
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 11:11 |
|
|
marie m
Eroberer
Dabei seit: 08.06.2013
Beiträge: 57
|
|
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 13:42 |
|
|
Karlito
Kaiser
Dabei seit: 11.04.2011
Beiträge: 1.461
|
|
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 20:06 |
|
|
marie m
Eroberer
Dabei seit: 08.06.2013
Beiträge: 57
|
|
Vielen Dank für deine Hilfe!!!
|
|
25.01.2014 01:35 |
|
|
|