Geschrieben von Karlito am 14.03.2012 um 20:05:
Hallo,
das beste ist meist, wenn man Dinge, die man schon kennt wiederverwendet
Du kennst ja bereits eine Grammatik für die Sprache
Noch ein kleiner Tipp:
Und nun nur noch ein wenig Lego
(Hab auch 15-30 min gebraucht)
Zum Nachweis:
für Kontextfreie Sprachen gilt, dass ein Kellerautomat angebbar sein muss. Hier kann einer angegeben werden der folgendermaßen funktioniert:
- Lege Elemente auf den Keller solange a gelesen werden.
- Entferne Elemente vom Keller solage b gelesen werden und Kellerstartsymbol nicht erreicht ist
- Bei erreichen des Kellerstartsymbols, lege neue Kellersymbole auf den Keller, solange b gelesen wird
- Lösche Kellersymbole, solange a gelesen wird.
- Akzeptiere wenn eingabe = epsilon und Kellerstartsymbol auf dem Keller...
Wobei es schwierig sein kann, einen solchen Automaten anzugeben. Der Nachweis, dass eine Sprache definitiv nicht Kontextfrei ist, lässt sich über das
Pumping-Lemma für Kontextfreie Sprachen führen.
VG,
Karlito
Geschrieben von Karlito am 14.03.2012 um 21:11:
Hallo Lisa,
ich dachte du hättest die Sprache anhand deiner
anderen Frage bereits erkannt.
Es kann natürlich sein, dass ihr Kellerautomaten noch nicht hattet. Dann vergiss einfach was ich darüber geschrieben habe. Was den Nachweis der Nichterkennbarkeit angeht, kenne ich keine andere Methode.
Ich denke jetzt sollte es klarer sein, oder?
VG,
Karlito