Hallo, ich weiß noch nich genau wie ich einen Kellerautomaten aufzeichnen soll, was ich an die Kanten schreibe…damit es formal richtig ist.
Könnet mir jemand vielleicht die Lösung der zweiten Präsenzaufgabe zeigen?
Konstruieren sie einen Kellerautomaten der Sprache L := {0^n 1^2n | n > 0}
Vielen Dank
die Zustände werden ganz normal aufgezeichnet und ein Zustandsübergang hat die Form:
(a, 1) -> 110 (so wirds im Skript gemacht)
oder auch
a, 1 | 110 (so haben wir es in den Übungen gemacht)
das a ist vom Eingabeband
die 1 ist vom Keller (und wird auch vom Keller heruntergenommen)
110 wird auf den Stack geschrieben (die 1 ist danach ganz oben)
Wenn du dir trotzdem nicht sicher bist mit dem Zeichnen des Automaten schreib ihn doch einfach als 7-Tupel auf. Wie das auszusehen hat steht ja auf jeden Fall in den Folien.
die Zustände werden ganz normal aufgezeichnet und ein Zustandsübergang hat die Form:
(a, 1) -> 110 (so wirds im Skript gemacht)
oder auch
a, 1 | 110 (so haben wir es in den Übungen gemacht)
das a ist vom Eingabeband
die 1 ist vom Keller (und wird auch vom Keller heruntergenommen)
110 wird auf den Stack geschrieben (die 1 ist danach ganz oben)
Wenn du dir trotzdem nicht sicher bist mit dem Zeichnen des Automaten schreib ihn doch einfach als 7-Tupel auf. Wie das auszusehen hat steht ja auf jeden Fall in den Folien.
also ist die 1 das was ich vom Keller herunter nehme?
und das nach dem | ist das was man dann auf den Keller raufschreibt?
hat jemand vielleicht den Graphen zur Aufgabe dazu?
sonst muss ich mich wohl doch durch das skript quälen… und danach merkt man dann es geht ja auch viel einfacher zu erklären….
die 1 ist das, was du vom Keller herunter nimmst
die Präsenzaufgabe sieht fast genauso aus, wie die Aufgabe im Skript. Siehe Anhang. Für jede Null werden 2 as auf den Stack gepackt und für jede Eins wird ein a vom Stack genommen, so dass man am ende doppelt so viele Einsen wie Nullen hat.
ok, die logik ist schon klar, nun verstehe ich nicht warum in q_0 steht: (0,a)->aaa, warum 3 a? was ist nochmal genau der ausdruck nach dem -> ?
ok, die logik ist schon klar, nun verstehe ich nicht warum in q_0 steht: (0,a)->aaa, warum 3 a? was ist nochmal genau der ausdruck nach dem -> ?
Das eine 'a' wird vom Keller entfernt und stattdessen drei 'a's, also 'aaa' hingeschrieben.
Das sind also jeweils 2 zusätzliche 'a's bei jedem Übergang, gell?
kommt dieser automat nur in den endzustand, wenn er nach doppelt so viel einsen wie nullen das leere wort gelesen hat? aber das macht er ja sowieso wenn das eingabeband zu ende ist, oder? oder wie muss man den letzten übergang verstehen?
kommt dieser automat nur in den endzustand, wenn er nach doppelt so viel einsen wie nullen das leere wort gelesen hat?
genau so ist es. Wenn der Automat im Endzustand ist ist außerdem noch der Keller leer, das heißt das Wort ist nach jeder definition akzeptiert.
Bzw. das epslion bedeutet eigentlich nicht, dass das leere Wort gelesen wird, sondern das das Eingabeband nicht weiterläuft. Das leere Wort kann also zwischen jedem Buchstaben gelesen werden.
