Informatiker Board | Automatentheorie | Deterministischen pushdown automat

Informatiker Board » Themengebiete » Theoretische Informatik » Automatentheorie » Deterministischen pushdown automat

» Hallo Gast [Anmelden|Registrieren]

Letzter Beitrag | Erster ungelesener Beitrag

Druckvorschau | An Freund senden | Thema zu Favoriten hinzufügen

Deterministischen pushdown automat

Autor

Beitrag

« Vorheriges Thema | Nächstes Thema »

marie m
Eroberer

Dabei seit: 08.06.2013
Beiträge: 57

Deterministischen pushdown automat

Zitatantwort auf diesen Beitrag erstellen

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

Nehmen Sie marie m in Ihre Freundesliste auf

Karlito Karlito ist männlich

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

Nehmen Sie Karlito in Ihre Freundesliste auf

marie m
Eroberer

Dabei seit: 08.06.2013
Beiträge: 57

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

Dieser Beitrag wurde 1 mal editiert, zum letzten Mal von marie m: 08.01.2014 19:23.

08.01.2014 15:26

Karlito Karlito ist männlich

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:
$[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

12.01.2014 01:55

Karlito Karlito ist männlich

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 Karlito ist männlich

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

marie m
Eroberer

Dabei seit: 08.06.2013
Beiträge: 57

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?

Dieser Beitrag wurde 2 mal editiert, zum letzten Mal von marie m: 14.01.2014 11:07.

14.01.2014 10:51

Karlito Karlito ist männlich

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 Karlito ist männlich

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

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

Dieser Beitrag wurde 1 mal editiert, zum letzten Mal von marie m: 14.01.2014 22:26.

14.01.2014 22:25

Karlito Karlito ist männlich

Kaiser

Dabei seit: 11.04.2011
Beiträge: 1.461

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:

15.01.2014 16:31

marie m
Eroberer

Dabei seit: 08.06.2013
Beiträge: 57

Vielen Dank für deine Hilfe!!!

25.01.2014 01:35

Baumstruktur | Brettstruktur

Informatiker Board » Themengebiete » Theoretische Informatik » Automatentheorie » Deterministischen pushdown automat