Erkennen kontextfreier Sprachen

Neue Frage »

Auf diesen Beitrag antworten »
deppensido Erkennen kontextfreier Sprachen

Hallo,

bei der Aufgabe würde ich sagen, dass die Sprache nicht kontextfrei ist, weil es zwei Variablen n und m gibt die gespeichert werden müssten, was darauf hinweist, dass die Sprache nicht kontextfrei ist.

Also Wort für das Pumping Lemma würde ich dann: a^2p b^p c^p wählen.

Ist das richtig? Gibt es vielleicht noch andere Indizien die darauf hinweisen, dass eine Sprache nicht kontextfrei ist?

Vielen Dank schon mal.

Grüße
 
Auf diesen Beitrag antworten »
deppensido

hallo, nochmal.

Ich glaube mittlerweile, dass meine Annahme falsch ist. Da mit dem Wort w=a^2p b^p c^p mit w = uvxyz bel. Aufteilung von w und |vxy| <= p und |vy| >= 1, klappt das Pumping Lemma für den Fall: v enthält a's und y enthält b's nicht. Da bei egal welcher Wahl von i : uv^i xy^i z in der Sprache liegt. Passt das?

Weiterhin Tipps, wie ich eine kontextfreie Sprache erkenne, wären sehr gut.

Grüße
Auf diesen Beitrag antworten »
Karlito

Hallo,

die Sprache ist Kontextfrei. Man kann einen PDA angeben, der die Sprache akzeptiert.

Die Summe der Anzahl b und c entspricht genau der Anzahl von a. Somit baust du deinen Stack auf, solange du a liest und baust ihn ab, während du b und c liest. Die Bedinung, dass m <=n sein muss wird erfüllt, wenn du mindestens ein c liest. Nach dem letzten c muss der Stack leer sein.

VG,

Karlito
Auf diesen Beitrag antworten »
deppensido

hallo,

ich habe die Aufgabe nun, wie du beschrieben hast, mit nem PDA gelöst, wobei dieser beim Lesen der a's n 0en auf den Stack legt und beim lesen der b's und c's wieder geleert wird.

Kannst du mir vielleicht noch ein paar allgemeine tipps geben, wie ich ganz schnell erkenne, ob eine Sprache kontextfrei ist oder nicht. In der Klausur ist nicht viel Zeit zum rumprobieren.

Grüße
 
Auf diesen Beitrag antworten »
Karlito

Hi,

ich kann leider nicht wirklich Tipps geben. Hier war es sehr einfach, weil man nur einen "Zähler" braucht, welcher sich durch den Stack realisieren lässt. Z.b. bei a^nb^nc^n müsstest du den selben "Zähler" zwei mal verwenden. Das ist jedoch bei einem PDA nicht möglich... Das ist so in etwa die Heuristik, mit der ich an soetwas herangehe.

Für reguläre Sprachen versuche ich mir immer den Automaten zu konstruieren... Wenn man sich den nicht vorstellen kann, muss dann leider das Pumping-Lemma ran... (ich und das Pumping Lemma sind jedoch leider nie Freunde geworden großes Grinsen ).

Auf kontextsensitive Sprachen sind wir irgendwie nur am Rande eingegangen, somit kann ich dazu wenig sagen. (Ohne im Skript zu blättern)

Typ 0 Sprachen werden ja von Turingmaschinen erkannt. Hier sind Halteproblem und Entscheidbarkeit die Stichworte... Da gilt es "einfach" die Beispiele zu kennen und einordnen zu können. Also vorwiegend das allgemeine Halteproblem und daraus hervorgehend die speziellen Halteprobleme und Satz von Rice. Die Aufgaben bezogen sich meist auf Reduktionen. Da weiß ich jedoch nicht wie Tiefgehend das bei euch behandelt wurde.

VG,

Karlito
Auf diesen Beitrag antworten »
deppensido

hallo,

ich hab gemerkt, dass ich das Pumping Lemma im Kopf schnell durchgehen kann und so schauen kann, ob es passt. Das Wort zu wählen ist ja in der Regel ganz einfach und dann kann man schnell den Fall durchgehen, bei den man glaubt, dass es schief gehen könnte. In diesem Fall war das: v enthält b's und y etnhält c's. Habs gerade mit einer ähnlichen Aufgabe getestet.

Reduktionen werden in der Klausur auch eine große Rolle spielen. Damit darf ich mich dann jetzt noch beschäftigen. Grüße
 
Neue Frage »
Antworten »


Verwandte Themen

Die Beliebtesten »
Die Größten »
Die Neuesten »