Vorgehensweise bei dieser Aufgabe?

Question

Hallo,

könnte jemand freundlicherweiße das Vorgehen bei dieser Aufgabe erläutern?

Mir ist nicht so ganz klar wie ich bei Aufgaben diesen Typs herangehen muss, um den Kellerautomaten anzugeben. Insbesondere die ganzen Übergänge die man definiert.

Vielen Dank!

 

Answer 1

Hallo,

ein genaues "Rezept" gibt es bei solchen Aufgaben nicht, vieles kommt erst mit der Zeit, wenn man viele Aufgaben gesehen hat. Eventuell kann eine Skizze des Kellers ganz hilfreich sein.

Die Herangehensweise in dieser Aufgabe ist so ähnlich wie in der VL (bzw. auf der Einführungsfolie im Tut), dort wurde ein KA konstruiert für Wörter der Form (a^n)(b^n). Dort hat man zuerst alle a's in den Keller geschrieben und anschließend für jedes b das man eingelesen hat, ein a aus dem Keller gestrichen. Wenn der Keller am Ende leer und das Wort zuende war, dann wusste man, dass das Wort genausoviele a's wie b's hatte.

Der einzige Unterschied in dieser Aufgabe ist, dass die 0er und 1er in beliebiger Reihenfolge auftauchen können. Das heißt, dass das, was man in den Keller reinschreibt, abhängt von dem Zeichen das man in s0 einliest.

Beim Definieren der Übergänge kannst du dir zuerst überlegen, ob lambda in der Sprache liegt (d.h. s0 = Endzustand = gleich viele 1er & 0er). Danach kannst du schrittweise parallel zu einer Skizze überlegen, wie du deine Übergänge definieren willst.

Bsp.: 0110. Wenn du eine 0 reinmalst, dann solltest du in s1 wechseln, da sonst das Wort 0 auch akzeptiert werden würde. Danach bietet es sich an, die 0 zu streichen wenn eine 1 folgt. Dann ist der Keller leer und im bisherigen Teilwort gab es genauso viele 0er wie 1er. Deswegen wechselst du zurück in s0 mit (s1,lambda,k0) -> (s0,k0). So kannst du dann weiter verfahren und auf eine Lösung kommen :)

Viele Grüße,

Vivian (Tutor)