Kontextfrei Sprache-Abschlusseigenschaften

Neue Frage »

02.01.2014, 01:51	Auf diesen Beitrag antworten »
marie m	Kontextfrei Sprache-Abschlusseigenschaften Hallo und Frohes Neues Jahr!!! Könnt ihr mir sagen wie man mit den Abschlusseigenschaften zeigen kann dass die Sprache L={w in {a,b}*: w=a^i b^j, i != j} kontextfrei ist ?


02.01.2014, 23:36	Auf diesen Beitrag antworten »
Karlito	Hallo, mir fällt leider dazu nichts ein. Ist es explizit gefordert, dass man es über die Abschlusseigenschaften nachweisen soll? VG, Karlito
03.01.2014, 01:13	Auf diesen Beitrag antworten »
marie m	Ja, es ist gefordert dass man es über die Abschlusseigenschaften nachweisen soll. Ich habe eine Idee aber ich weiss nicht ob sie richtig ist. Könnte man vielleicht die Union der folgenden Sprachen nehmen? {w in {a,b}: w=a^i b^j, i < j} UND {w in {a,b}: w=a^i b^j, i > j}
03.01.2014, 21:34	Auf diesen Beitrag antworten »
Karlito	Hallo Marie, prinzipiell stimmt diese Aussage. Dazu musst du aber bewiesen haben, dass beide verwendeten Sprachen kontextfrei sind. Oder Du musst es als Fakt heranziehen dürfen. Der Beweis, die Sprachen kontextfrei sind, ist eigentlich auch einfach, da man für beide Sprachen leicht einen Kellerautomaten konstruieren kann. Dann wäre der Beweis aber nicht nur über Abschlusseigenschaften geführt. Das hat mich daran gehindert die Lösung in betracht zu ziehen. Vielleicht denke ich da aber auch zu kompliziert. Das solltest Du am Besten einschätzen können, da Du den Dozenten und seinen Anspruch kennst. VG, Karlito
Anzeige

04.01.2014, 02:53	Auf diesen Beitrag antworten »
marie m	Ja, ich muss Sprachen verwenden die kontextfrei sind, ohne es zu beweisen. Bei der Aufgabe stehen als Beispiel solcher Sprachen die Folgende: - {a^i b^j, i >=1} - {a^i , i >=1} - {a,b}^{+} - Reguläre Sprachen Wie könnte ich diese Sprachen mit der L={w in {a,b}*: w=a^i b^j, i != j} verbinden?
04.01.2014, 03:25	Auf diesen Beitrag antworten »
Karlito	Hallo Marie, ich denke damit ist die Aufgabe gelöst. Du verwendest eine Sprache die kontextfrei ist, ohne beweisen zu müssen, dass sie kontextfrei ist. Kontextfreie Sprachen sind unter Vereinigung abgeschossen... Das sollte es gewesen sein. Edit: - Du verwendest zwei Sprachen, die Kontextfrei sind! - Die Beispiele sind fies, da die drei oberen auch reguläre Sprachen sind Edit2: Ich hoffe es wird durch den Edit nicht unverständlich, sonst bitte gerne noch mal nachhaken! VG, Karlito
05.01.2014, 01:16	Auf diesen Beitrag antworten »
marie m	Also kann ich keins dieser Beispiele für diese Sprache verwenden ?
05.01.2014, 19:04	Auf diesen Beitrag antworten »
Karlito	Ich sehe da keinen Weg... Edit: Etwas konkreter: a^jb^i mit i!=j ist eine kontextfreie, aber nicht reguläre Sprache. Da die Beispiele alle regulär sind (bei dem ersten Beispiel ist es nicht eindeutig, da j nicht definiert ist) und reguläre Sprachen unter allen Operationen abgeschlossen sind kann daraus keine kontextfreie Sprache entstehen. VG, Karlito
06.01.2014, 13:27	Auf diesen Beitrag antworten »
marie m	Ok! Ich habe noch eine Frage... Ist die Sprache {w in {a,b}: w=a^i b^j, i != j} die selbe wie die Sprache {w in {a,b}: w != a^i b^i, i >=0} ?
06.01.2014, 15:53	Auf diesen Beitrag antworten »
Karlito	Hallo, nein! In der ersten Sprache müssen ja i und j unterschiedlich sein und in der zweiten hat die Potenz immer den selben Wert. D.h. in der zweiten Sprache sind ab, aabb, ... enthalten, in der ersten aber eben genau nicht! Aber Achtung! $[latex]L=\{a,b\}^* \setminus \{a^ib^i~\|~i>=0\} [/latex]$ kann nicht verwendet werden, da kontextfreie Sprachen unter Komplement nicht abgeschlossen sind. VG, Karlito
06.01.2014, 16:08	Auf diesen Beitrag antworten »
marie m	Mit der zweite Sprache meine ich: $[latex] \{w \in \{a,b\}^{}: w \neq a^i b^i, i >=0\} [/latex]$ Bedeutet das nicht das die Anzahl von a nicht die gleiche sein soll wie die Anzahl von b? Das bedeutet nicht auch die Sprache $[latex] \{w \in \{a,b\}^{}: w = a^i b^j, i \neq j \} [/latex]$ ?
06.01.2014, 19:25	Auf diesen Beitrag antworten »
Karlito	Oh, sorry, verlesen... Ja, das sind gleiche Sprachen.
06.01.2014, 22:16	Auf diesen Beitrag antworten »
marie m	Kann von der Sprache $[latex]\{w \in \{a,b\}^{*}: w \neq a^i b^i, i \geq 0\} [/latex]$ das Wort entstehen? Das Wort soll nur nicht die Form oder haben, oder?
06.01.2014, 22:20	Auf diesen Beitrag antworten »
Karlito	Genau
06.01.2014, 22:24	Auf diesen Beitrag antworten »
marie m	Also sind die zwei Sprachen doch nicht die selben? Oder verstehe ich es falsch?
07.01.2014, 20:31	Auf diesen Beitrag antworten »
Karlito	Du verstehst das richtig.Die beiden Sprachen sind gleich. VG, Karlito

Neue Frage »

Antworten »

Kontextfrei Sprache-Abschlusseigenschaften

Verwandte Themen