Geschrieben von Karlito am 31.03.2015 um 13:34:
Hallo Jannes,
ich habe auch eine Weile nachdenken müssen. Rein intuitiv ist ja schon einmal klar, dass es eine kontextfreie Grammatik geben muss, da man relativ leicht einen Kellerautomaten konstruieren kann, welcher die Sprache akzeptiert. D.h. es muss eine kontextfreie Grammatik geben. Nur wie man diese erstellt ist ein wenig kniffelig.
Tragen wir unser wissen zusammen:
- Es ist das leere Wort in der Sprache, wenn k=0 und n=0 sind.
- Wenn n = 0, dann ist die Sprache
- Wenn n > 0, dann gibt es n mehr a am Anfang als am Ende.
Man kann die Sprache also auch folgendermaßen auffassen:
Das macht uns die Erstellung der Grammatik ein wenig einfacher.
Bis man selbst auf solche Lösungen kommt, braucht es etwas Übung und Kreativität. Es gibt sicher noch andere korrekte Lösungen. Die Begründung, warumdiese Grammatik korrekt ist, sollte dir jetzt nicht allzu schwer fallen.
Falls noch etwas unklar ist, bitte nachfragen.
Gruß,
Karlito