Informatiker Board | Automatentheorie | Kellerautomaten erzeugen

Informatiker Board » Themengebiete » Theoretische Informatik » Automatentheorie » Kellerautomaten erzeugen

» Hallo Gast [Anmelden|Registrieren]

Letzter Beitrag | Erster ungelesener Beitrag

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

Kellerautomaten erzeugen

Autor

Beitrag

« Vorheriges Thema | Nächstes Thema »

deppensido
Doppel-As

Dabei seit: 23.12.2012
Beiträge: 144

Kellerautomaten erzeugen

Zitatantwort auf diesen Beitrag erstellen

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

deppensido hat dieses Bild (verkleinerte Version) angehängt:

19.01.2013 23:35

Nehmen Sie deppensido in Ihre Freundesliste auf

Karlito Karlito ist männlich

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 [latex]L_1[/latex]

dem Fall prüfen, dass nachdem der Keller leer ist, noch mindestens eine 1 und keine 0 folgt.

[latex]L_2[/latex]

überlasse ich mal dir.

Ich hoffe ich konnte helfen.

VG,

Karlito

20.01.2013 15:52

Nehmen Sie Karlito in Ihre Freundesliste auf

deppensido
Doppel-As

Dabei seit: 23.12.2012
Beiträge: 144

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?

deppensido hat dieses Bild (verkleinerte Version) angehängt:

20.01.2013 20:58

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

deppensido
Doppel-As

Dabei seit: 23.12.2012
Beiträge: 144

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

deppensido hat dieses Bild (verkleinerte Version) angehängt:

20.01.2013 22:06

Karlito Karlito ist männlich

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

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

Kaiser

Dabei seit: 11.04.2011
Beiträge: 1.461

Hallo,

nein, ich habe Aufgabe 1a betrachtet. Und bei [latex]0^n1^m[/latex]

mit n=3 und m=1 ist $[latex]3 > 2\cdot 1[/latex]$ . 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 traurig

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

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 smile

24.01.2013 22:56

Karlito Karlito ist männlich

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

Baumstruktur | Brettstruktur

Informatiker Board » Themengebiete » Theoretische Informatik » Automatentheorie » Kellerautomaten erzeugen