Hallo,

in Aufgabe 12.2 ist eine Sprache gegeben und zu der soll man einen Kellerautomaten angeben…..hm….grübel grübel…….hab mir dann überlegt, dass es ja eine kontextfreie Grammatik zu der Sprache gibt und dann kann man ja nach Theorem 5.12 zu jeder CfG effektiv ein Kellerautomaten konstruieren……..weiss jetzt net, ob das so stimmt…….

gruss
anonymer user

jo stimmt…

Es ist aber gut möglich, dass die Grammatik recht kompliziert wird, wodurch der Beweis (dass die Grammatik wirklich die Sprache generiert - und damit letztendlich auch der nach dem Theorem konstruierte Automat die Sprache akzeptiert) schwieriger wird, als wenn man eine gute Idee für den Automaten hat!

Ausserdem sollte man sich vielleicht wirklich einen Automaten überlegen, um dies zu üben. Die Idee die dahinter steckt (die Art zu "zählen") kann man auch bei anderen Sprachen einsetzen.

Cheers.