Kellerautomaten erzeugen |
| 19.01.2013, 23:35 | Auf diesen Beitrag antworten » |
| deppensido | Kellerautomaten erzeugen Hallo, zu der Aufgabe im Anhang soll man einen Kellerautomaten erzeugen. Wie ein PDA funktioniert weiß ich zwar, mir will aber keine informelle Beschreibung für diesen einfallen. Wie kann man z.B. die 2m realisieren? Ich hoffe mir kann jemand auf die Sprünge helfen. Grüße |
|
|
|
| 20.01.2013, 15:52 | Auf diesen Beitrag antworten » |
| Karlito | 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 Ich hoffe ich konnte helfen. VG, Karlito |
| 20.01.2013, 20:58 | Auf diesen Beitrag antworten » |
| deppensido | hallo, zu 1a) habe ich aufgrund deiner Informationen meine Lösung hochgeladen. Folgendes hab ich dabei überlegt: q0 ist der Startzustand, q1 und q5 Endzustände. Zuerst lege ich § auf den Stack, um den Boden zu markieren. Da n,m >= 0, ist q1 ein Endzustand, da nicht zwingend Einsen benötigt werden. Dann habe ich mit q2 und q3 versucht die 2m für die Einsen zu realisieren. Sind keine Einsen mehr vorhanden, geht es mit q3 nach q4 weiter, falls noch mindestens eine 0 auf dem Band ist. Diese wurden beim Lesen der Einsen ja gelöscht, aber nach Definition von L1 müssen ja mehr Nullen als Einsen vorkommen. In q4 wird der Stapel dann entleert und ist das Bodensymbol § erreicht geht es in den Endzustand q5. Alles so richtig? |
| 20.01.2013, 21:47 | Auf diesen Beitrag antworten » |
| deppensido | Ich hab gerade festgestellt, dass meine Lösung noch nicht korrekt ist. Ich arbeite gerade an einer neuen. Grüße |
| Anzeige | |
|
|
|
| 20.01.2013, 22:06 | Auf diesen Beitrag antworten » |
| deppensido | so, im Anhang ist jetzt die korrigierte Version. Beim ursprünglichen durfte schon q1 kein Endzustand sein, da dann z.B. das leere Wort, was nicht in L1 liegt akzeptiert werden würde. Zudem hatte ich nicht geprüft, ob mindestens eine 0 gelesen wird. Wegen n > 2m muss 0 ja mindestens einmal vorkommen. Hoffe es stimmt jetzt so. Grüße |
| 21.01.2013, 17:50 | Auf diesen Beitrag antworten » |
| Karlito | Ich komme leider erst morgend dazu, mich darum zu kümmern. VG, Karlito |
| 22.01.2013, 12:46 | Auf diesen Beitrag antworten » |
| Karlito | 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, 14:35 | Auf diesen Beitrag antworten » |
| deppensido | 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:48 | Auf diesen Beitrag antworten » |
| Karlito | Hallo, nein, ich habe Aufgabe 1a betrachtet. Und bei VG, Karlito |
| 22.01.2013, 15:30 | Auf diesen Beitrag antworten » |
| deppensido | 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:38 | Auf diesen Beitrag antworten » |
| deppensido | 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, 16:21 | Auf diesen Beitrag antworten » |
| Karlito | 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 |
| 24.01.2013, 22:56 | Auf diesen Beitrag antworten » |
| deppensido | 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, 23:05 | Auf diesen Beitrag antworten » |
| Karlito | 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 |
|
|
