Kellerautomat
-
Lieber µ,
das ist echt eine geniale Lösung!
THX!
L. G.
Steffo
-
Gern geschehen
-
Ich habe hier eine Aufgabe mit Musterlösung von der ich denke, dass letztere falsch ist.
"Konstruieren Sie einen Kellerautomaten, der alle Wörter über {a, b} akzeptiert, die genau doppelt so viele a’s wie b’s enthalten."
Lösung:
"Da die Reihenfolge unbekannt ist, können nur entweder a’s oder b’s in den Keller gestopft werden. Für je ein b packe ich 2 a’s in den Keller bzw. hole 2 a’s heraus. Aufpassen: auch in Fällen wie abbaaa muß richtig verfahren werden!"
q0 b # --> qb aa# q0 a # --> qa a# qb b a --> qb aaa qb a a --> qb [e]epsilon[/e] qb b # --> qb aa# qb a # --> qa a# qb [e]epsilon[/e] # --> qf [e]epsilon[/e] fertig qa a a --> qa aa qa b a --> qc [e]epsilon[/e] 1. a löschen qc [e]epsilon[/e] a --> qa [e]epsilon[/e] 2. a löschen, falls vorhanden qa [e]epsilon[/e] # --> qf [e]epsilon[/e] fertig qc [e]epsilon[/e] # --> qd # keine a’s mehr vorhanden qd a # --> q0 # qd b # --> qb aaa#So viel zur Musterlösung. Ich habe dazu ein Beispiel konstruiert:
a a a a b b qo qa qa qa qa qc (*) # # # # # # a a a a a a a a a a a a a (*) qc mit Eingabe b ist nicht vorgesehen!Sehe ich das richtig, dass diese Lösung falsch ist?
L. G.
Steffo
-
Ich habe dazu eine eigene Lösung entwickelt. Die Idee: Da es doppelt so viele a's wie b's geben muss, füge ich beim Lesen von einem b einfach zwei b's ein und später prüfe ich, ob es gleich viele b's wie a's gibt.
Meine Lösung: q0 b # --> q1 bb# q0 a # --> q1 a# q1 a a --> q1 aa q1 b b --> q1 bbb q1 b a --> q1 [e]epsilon[/e] q1 a b --> q1 [e]epsilon[/e] q1 [e]epsilon[/e] # --> qf [e]epsilon[/e] Endzustand
-
1.) Keiner weiss, was deine kryptische Darstellung/Tabelle bedeutet oder wie sie zu interpretieren ist.
2.) Der Automat arbeitet fuer dein Beispiel korrekt ... wegen dem Epsilonuebergang, b braucht nicht in qc gelesen werden.
-
Wenn ich alle a's eingelesen habe, bin ich immernoch im Zustand qa und lese ein b. Daraufhin pope ich (ε) und gehe in den Zustand qc. Es folgt jedoch ein weiteres b, aber es ist keine Anweisung im Zustand qc definiert in der man ein b einlesen kann.
BTW: Meine Lösung ist doch auch richtig, oder? Und nicht nur das, sie ist deutlich einfacher.
L. G.
Steffo
-
Es folgt jedoch ein weiteres b, aber es ist keine Anweisung im Zustand qc definiert in der man ein b einlesen kann.
Du verstehst nicht. Es wird epsilon in diesem Fall eingelesen ... das Eingabewort wird nicht veraendert. Gleiches Konzept wie bei Nichtdeterministischen endlichen Automaten, nur eben mit Stack.
a a a a b b ist aequivalent zu a a a a b ε b , ein epsilon kann ueberall nach Bedarf "eingefuegt" werden.
PS: Ich werde deine Loesung nicht ueberpruefen, da ich immer noch nicht weiss, was die Tabelle im Detail bedeutet.
-
knivil schrieb:
Du verstehst nicht. Es wird epsilon in diesem Fall eingelesen ... das Eingabewort wird nicht veraendert. Gleiches Konzept wie bei Nichtdeterministischen endlichen Automaten, nur eben mit Stack.
a a a a b b ist aequivalent zu a a a a b ε b , ein epsilon kann ueberall nach Bedarf "eingefuegt" werden.
THX! PS: Ich werde deine Loesung nicht ueberpruefen, da ich immer noch nicht weiss, was die Tabelle im Detail bedeutet.
Beispiel: q a A --> p b
Leseweise: „Wenn KA im Zustand q ist und a liest und zuoberst im Keller A ist, so geht er in Zustand p und schreibt b“
-
Leseweise: „Wenn KA im Zustand q ist und a liest und zuoberst im Keller A ist, so geht er in Zustand p und schreibt b“
Das ist klar. Nimmt er beim Lesen von A das selbige auch gleich vom Stack?
-
Ja.
EDIT: Zwei Konstellationen hatte ich noch vergessen. Ich habe sie mal ergänzt (die beiden letzten Zeilen)
q0 b # --> q1 bb# q0 a # --> q1 a# q1 a a --> q1 aa q1 b b --> q1 bbb q1 b a --> q1 [e]epsilon[/e] q1 a b --> q1 [e]epsilon[/e] q1 [e]epsilon[/e] # --> qf [e]epsilon[/e] Endzustand q1 b # --> q1 b# q1 a # --> q1 a#