Kellerautomaten erzeugen |
Karlito
Kaiser
Dabei seit: 11.04.2011
Beiträge: 1.461
|
|
Hallo,
der Kellerautomat erweitert den DEA um eine eingeschränkte Möglichkeit zählen zu können. Das kann realisiert werden, indem bei jedem Schritt ein Kellerspeicher gefüttert werden kann.
Der Begriff Keller ist an dieser Stelle manchmal ein wenig verwirrend, weil er die Art des Speichers schlecht beschreibt. Ich weiß nicht, wie der Begriff entstanden ist. Besser ist hier Stapelspeicher. Dabei ist der Stapel als Papierstapel zu verstehen. Neue Datensätze können nur darauf gelegt werden und beim Speicherzugriff kann nur das oberste Element entnommen werden.
Hast du nun die Sprache a^n b^n. Dann würde ein Kellerautomat so funktionieren, dass für jedes a ein Element auf den Keller gelegt werden. Nennen wir es X. Für die Akzeptanz wird nun für jedes a ein X auf den Keller gelegt und sobald ein b auftritt, dann wird immer je b ein X vom Keller entfernt. Das wird solange gemacht. Der Automat geht in den akzeptierenden Zustand über wenn nur b gelesen wurden, das Wort zuende ist und der Keller genau Leer ist.
Bei 2m musst du pro Kellerelement einfach nur 2 Zeichen lesen (du brauchst dafür einen Zwischenzustand), und Du musst für dem Fall prüfen, dass nachdem der Keller leer ist, noch mindestens eine 1 und keine 0 folgt.
überlasse ich mal dir.
Ich hoffe ich konnte helfen.
VG,
Karlito
|
|
20.01.2013 15:52 |
|
|
deppensido
Doppel-As
Dabei seit: 23.12.2012
Beiträge: 144
|
|
Ich hab gerade festgestellt, dass meine Lösung noch nicht korrekt ist. Ich arbeite gerade an einer neuen.
Grüße
|
|
20.01.2013 21:47 |
|
|
Karlito
Kaiser
Dabei seit: 11.04.2011
Beiträge: 1.461
|
|
Ich komme leider erst morgend dazu, mich darum zu kümmern.
VG,
Karlito
|
|
21.01.2013 17:50 |
|
|
Karlito
Kaiser
Dabei seit: 11.04.2011
Beiträge: 1.461
|
|
Hallo,
deine Lösung funktioniert leider nicht. Prüfe mal das Wort 0001.
Probier mal pro gelesener 1 zwei Elemente vom Keller zu nehmen.
Betrachte außerdem noch den Fall 00010. Dieses Wort sollte nicht akzeptiert werden (habe ich jetzt nicht durchdacht, ob du das mit betrachtest hast).
VG,
Karlito
|
|
22.01.2013 12:46 |
|
|
deppensido
Doppel-As
Dabei seit: 23.12.2012
Beiträge: 144
|
|
hallo,
das Wort 0001 soll ja nicht akzeptiert werden, weil eingültiges wort 2m einsen braucht. 0001 wird bei mir nicht akzeptiert, weil ich bei nur einer 1 nicht von q3 nach q4 gelangen kann und somit auch den Endzustand nicht erreiche.
Das Wort 00010 wird bei mir auch nicht akzeptiert. Begründung, wie oben. Eine Eingabe z.B.: 0011110 kann auch nicht akzeptiert werden, denn um von q4 nach q5 zu kommen, muss das Wort vollständig gelesen sein und wenn nach einer 1 eine 0 folgt, bleibt der PDA in q4 stecken.
Naja, so denk ich mir das zumindest.
Hast du vielleicht Aufgabe 1b) betrachtet?
Grüße
|
|
22.01.2013 14:35 |
|
|
Karlito
Kaiser
Dabei seit: 11.04.2011
Beiträge: 1.461
|
|
Hallo,
nein, ich habe Aufgabe 1a betrachtet. Und bei mit n=3 und m=1 ist . Somit ist 0001 Element der gesuchten Sprache.
VG,
Karlito
|
|
22.01.2013 14:48 |
|
|
deppensido
Doppel-As
Dabei seit: 23.12.2012
Beiträge: 144
|
|
hallo,
dazu fällt mir erst mal ein: Mist! Ich habe die ganze Zeit die Sprache:
L={0^n1^2m | n> 2m, n,m >= 0} betrachtet. Heißt, ich habe fälschlicherweise wegen den 2m geglaubt, dass die Anzahl der Einsen gerade sein muss.
Damit es klappt müsste ich also von q2 direkt nach q4 gehen mit 1,0 ->E
und an q4 nach q4, dann 1,0->E. Der Zustand q3 fällt dann natürlich weg. Natürlich müsste man die Zustände dann neu nummerieren.
Blöderweise hab ich den Zettel bereits abgegeben und für 1b) habe ich den selben Logikfehler gemacht. Jetzt geh ich wohl leer aus und die ganze Mühe war umsonst
Grüße
|
|
22.01.2013 15:30 |
|
|
deppensido
Doppel-As
Dabei seit: 23.12.2012
Beiträge: 144
|
|
um die Bedingung einzuhalten müsste man pro gelesener 1 zwei 0en entfernen. Wie könnte man das anstellen? Geht z.B. 1,00 -> E ?
Punkte werd ich hierfür zwar nicht mehr bekommen, aber zur Klausurvorbereitung ist es sicherlich nicht unwichtig (Hab mich wieder aufgemuntert, zumindest weiß ich jetzt wie ein PDA funktioniert und falsch ist meiner ja nur, wegen dem Logikfehler)
Grüße
|
|
22.01.2013 15:38 |
|
|
Karlito
Kaiser
Dabei seit: 11.04.2011
Beiträge: 1.461
|
|
Hallo,
ich weiß nicht, ob 1,00->E erlaubt ist. Ich würde im Zweifel einen Zwischenzustand einführen:
1,0->E
E,0->E
VG,
Karlito
|
|
22.01.2013 16:21 |
|
|
deppensido
Doppel-As
Dabei seit: 23.12.2012
Beiträge: 144
|
|
hab heute die Musterlösung bekommen.
1,00 -E ist scheinbar wirklich nicht erlaubt, da die Musterlösung mit einem Zwischenzustand, wie du beschrieben hast, eingeführt wurde.
Hab erfreulicherweise noch 6 von 8 Punkten für die Aufgabe 1a + b erhalten
|
|
24.01.2013 22:56 |
|
|
Karlito
Kaiser
Dabei seit: 11.04.2011
Beiträge: 1.461
|
|
Schöne Sache, dass es so viele Punkte geworden sind. Im Script steht, dass immer nur der Zugriff auf das oberste Element erlaubt ist.
Danke für die Rückmeldung.
VG,
Karlito
|
|
24.01.2013 23:05 |
|
|
|