Ausführliche Erklärung des Schritts mit dem #

Question

Hi,

ab dem Schritt mit dem # verstehe ich den Kellerautomaten leider nicht mehr... kann mir jemand kurz erklären, was man sich bei den darauf folgenden Zeilen denken muss? Danke :)

 

Answer 1

Ab dem # kommt das zweite Teilwort v=a^l b^n a^m

Im Keller ist bereits das erste Teilwort u=a^i b^n a^k.

Jetzt kommen die ersten a's von v und löschen jeweils die letzten a's von u aus dem Keller. Aus der Aufgabenstellung weiß man dass l>k gelten muss. Deshalb müssen auch a's verarbeitet werden wenn bereits ein b als oberstes Kellerzeichen ausgegeben wird.

Dann werden die b's von u mit den b's von v rausgelöscht (genau gleich viele). Und am Schluss noch die letzten a's von v mit den ersten a's von u (wie oben).

Ich hoffe das war hilfreich. Wenn nicht noch mal etwas konkreter nachfragen.

Gruß Jörg (Tutor)

 

Answer 2

Hallo,

Ich machs mal komplett: Am Anfang schreibt man einfach alle Zeichen des ersten Teilwortes (u) in den Keller hinein. Der Übergang von s0 zu s1 erfolgt dabei, nachdem man nach dem b wieder ein a gelesen hat. Dies ist notwendig damit der Automat stoppt, wenn zB abab gelesen wird. Soweit ist es dir ja klar.

Das Trennzeichen wird dann nicht in den Keller geschrieben. Da alle Zeichen mindestens einmal enthalten sein sollen, weiß man, dass # auf jeden Fall gelesen wird, wenn ein a oben im Keller steht. (s1, #, a ) => (s2,a) heißt dann dementsprechend, dass der Keller nicht verändert wird und das oberste Zeichen einfach stehen bleibt (hier eben a). Außerdem erfolgt ein Zustandsübergang in s2, da wir uns nun im rechten Teilwort befinden (v).

Nun sollen die Wörter aus u nach dem b weniger a's haben, als v vor dem b. Für den Automaten heißt dies, dass wir für jedes a, welches wir nun lesen, die a's aus dem Keller löschen. (Zusätzliche Erklärung: Die a's, die oben im Keller stehen, sind ja die a's die in u nach dem b folgen. Hierzu einfach mal den Keller hinschreiben!)

Da nun ja die Zahl der a's, die wir im zweiten Teilwort gerade lesen echt größer sein soll, müssen wir ein b oben im Keller stehen haben UND noch a vom Eingabewort lesen. (unser Keller enthält also zu diesem Zeitpunkt (a^i b)). Wenn wir also in s2 sind und noch weiter a's von der Eingabe lesen und b im Keller steht, so machen wir mit den a's einfach nichts und lassen b oben stehen, außerdem wird in Zusant s3 gewechselt.

Wenn nun b (von der Eingabe) auf b (vom Keller) gelesen wird, so wechseln wir in s4, denn nun werden die b's gelöscht. Die Anzahl soll in Wörtern der Sprache ja für beide Teilwörter gleich lang sein. Somit müssen wir a auf a lesen, wenn alle b's im Keller und im Eingabewort abgearbeitet sind.

Nun sollen wieder mehr a's im rechten Teilwort sein, als im linken. Wir löschen also solange die a's, bis der Keller leer ist (k0 steht oben). Wird dann k0 im Keller gelesen, wird in den Endzustand (s5) gewechselt und es können noch beliebig viele weitere a's kommen.

Sooooo, ich hoffe das reicht dir als Erklärung ;)

Viele Grüße,

Julian (Tutor)

 

Comments

Eine allgemeine Frage dazu, da ich in meinem ersten Entwurf den Übergang von s0 auf s1 nicht hatte: Sind "zu viele" Zustände falsch - beispielsweise in dieser Aufgabe nach jedem neuen Buchstaben ein neuen Zustand? So könnte man diverse Eventualitäten abfangen. Mit Sicherheit ist es nicht die schönste Lösung.

LG & danke! :)