| Die letzten 10 Beiträge |
| marie m |
Vielen Dank für deine Hilfe!!! |
| 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
Karlito hat dieses Bild (verkleinerte Version) angehängt:
|
| marie m |
Damit ich das besser verstehe könntest du mir die Funktionsweise des Kellerautomaten beschreiben? |
| 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 |
| 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? |
| 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 |
| marie m |
| Zitat: |
Original von 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 |
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? |
| 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 |
| 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? |
| 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 |
| Es sind weitere Beiträge zu diesem Thema vorhanden. Klicken Sie hier, um sich alle Beiträge anzusehen. |
