Ist diese Sprache kontextfrei?
Hallo Leute,
ich frage mich, ob diese Sprache kontextfrei ist oder nicht. Wenn nicht, wie würde denn der Pumping Lemma Beweis dafür aussehen?
Vielen Dank im Voraus
1 Antwort
Die Sprache enthält alle Wörter gerader Länge für die gilt, dass wenn man das Wort in umgekehrter Reihenfolge aufschreibt, dass man dann bei keiner Position eine Übereinstimmung erhält.
Wenn zum Beispiel der erste Buchstabe a ist, muss der letzte Buchstabe b oder c sein.
Du kannst dafür leicht eine Kontextfreie Grammatik erzeugen, indem du die das Wort von innen nach außen aufbaust. Somit ist die Sprache kontextfrei.
Woher ich das weiß:Studium / Ausbildung – Mache derzeit meinen Mathematik Master