Kellerautomat

Hallo,
weiß jemand, wie man an diese Aufgabe herangeht?

"Entwerfen Sie einen Kellerautomaten, der die Wahl zum Semestersprecher auszählt:
Die Studenten Berti und Daniela haben kandidiert, die Studenten des Semesters haben jeweils mit einer Stimme gewählt. Der Name, der am Ende auf dem Stack liegt, hat die Wahl gewonnen."

Ich habe keine Ahnung wie ich da rangehen soll, zumal die Namen x-fach in jeder beliebigen Reihenfolge im Stack liegen können.
Ich kann ja immer nur den Momentanzustand erfassen, also das, was gerade eingelesen wird und das, was auf dem Stack liegt und dann entweder pushen oder popen.
Wie soll ich nun den Gewinner ermitteln, wenn mir nicht mal zwei Zähler zur Verfügung stehen?

Danke im Voraus für Ideen!

L. G.
Steffo

JingTho

ich nehme an zunächst ist alles auf dem stack aber geht auch in die andere Richtung.

pop solange bis alles weg ist,
falls kandidat 1 => zähler++
falls kandidat 2 => zähler--
am ende gucken ob unter 0 , 0 , oder über 0

dann wieder drau pobben :P, bis kandidat 1 oder kandidat je nach zähler kommt,
dann stoppen.

JingTho

JingTho schrieb:

ich nehme an zunächst ist alles auf dem stack aber geht auch in die andere Richtung.

pop solange bis alles weg ist,
falls kandidat 1 => zähler++
falls kandidat 2 => zähler--
am ende gucken ob unter 0 , 0 , oder über 0

dann wieder drauf pobben :P, bis kandidat 1 oder kandidat je nach zähler kommt,
dann stoppen.

falls 0 => nix drauf pobben.

Ein Zähler um -1 oder +1 zu verändern ist naheliegend aber formal wahrscheinlich auch sehr unbequem/schwer zu entwerfen.

Machen wir es lieber so: Eingabe ist aus dem Alphabet {B,D} und anfänglich ist der Keller leer.
Am Ende steht der Buchstabe des Gewinners mehrfach im Keller. Angenommen Berti gewinnt mit |B| Stimmen gegenüber |D| Stimmen, dann sollen am Ende |B|-|D| viele Symbole B im Keller stehen.

Fälle:
1. Keller ist leer: Dann wird das nächste Eingabezeichen gepusht
2. Es steht ein B oben im Keller und Eingabe ist B: Dann wird das zweite B dazugepusht.
3. Analog mit Keller-Top D und Eingabe D
4. Es steht ein B oben im Keller und Eingabe ist B poppen und nichts schreiben.
5. Analog mit Keller D und Eingabe B

Eingabe: {B,B,D,B,D,D,B,D,B,B,D,B}
Der Keller Verändert sich dann im Durchlauf wie folgt:
# //Anfangs leer
#B
#BB
#B
#BB
#B

#B

#B
#BB
#B
#BB

Also haben wir am Ende #BB im Keller, das heiß zwei Differenzstimmen plus für Berti -> Er gewinnt.

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

knivil

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

knivil

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“

knivil

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#