Informatiker Board | Druckvorschau: Kontextfrei Sprache-Abschlusseigenschaften

Geschrieben von marie m am 02.01.2014 um 01:51:

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 ?

Geschrieben von Karlito am 02.01.2014 um 23:36:

Hallo,

mir fällt leider dazu nichts ein. Ist es explizit gefordert, dass man es über die Abschlusseigenschaften nachweisen soll?

VG,

Karlito

Geschrieben von marie m am 03.01.2014 um 01:13:

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}

Geschrieben von Karlito am 03.01.2014 um 21:34:

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

Geschrieben von marie m am 04.01.2014 um 02:53:

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?

Geschrieben von Karlito am 04.01.2014 um 03:25:

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

Geschrieben von marie m am 05.01.2014 um 01:16:

Also kann ich keins dieser Beispiele für diese Sprache verwenden ?

Geschrieben von Karlito am 05.01.2014 um 19:04:

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

Geschrieben von marie m am 06.01.2014 um 13:27:

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} ?

Geschrieben von Karlito am 06.01.2014 um 15:53:

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

Geschrieben von marie m am 06.01.2014 um 16:08:

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]$ ?

Geschrieben von Karlito am 06.01.2014 um 19:25:

Oh, sorry, verlesen... Ja, das sind gleiche Sprachen.

Geschrieben von marie m am 06.01.2014 um 22:16:

Kann von der Sprache $[latex]\{w \in \{a,b\}^{*}: w \neq a^i b^i, i \geq 0\} [/latex]$ das Wort [latex] abab [/latex]

entstehen? Das Wort soll nur nicht die Form [latex] ab [/latex]

oder

haben, oder?