Informatiker Board | Theoretische Informatik | Kontextfrei Sprache-Abschlusseigenschaften

Informatiker Board » Themengebiete » Theoretische Informatik » Kontextfrei Sprache-Abschlusseigenschaften

» Hallo Gast [Anmelden|Registrieren]

Letzter Beitrag | Erster ungelesener Beitrag

Druckvorschau | An Freund senden | Thema zu Favoriten hinzufügen

Seiten (2): [1] 2 nächste »

Kontextfrei Sprache-Abschlusseigenschaften

Autor

Beitrag

« Vorheriges Thema | Nächstes Thema »

marie m
Eroberer

Dabei seit: 08.06.2013
Beiträge: 57

Kontextfrei Sprache-Abschlusseigenschaften

Zitatantwort auf diesen Beitrag erstellen

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 ?

Dieser Beitrag wurde 1 mal editiert, zum letzten Mal von marie m: 02.01.2014 01:51.

02.01.2014 01:51

Nehmen Sie marie m in Ihre Freundesliste auf

Karlito Karlito ist männlich

Kaiser

Dabei seit: 11.04.2011
Beiträge: 1.461

Hallo,

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

VG,

Karlito

02.01.2014 23:36

Nehmen Sie Karlito in Ihre Freundesliste auf

marie m
Eroberer

Dabei seit: 08.06.2013
Beiträge: 57

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 01:13

Karlito Karlito ist männlich

Kaiser

Dabei seit: 11.04.2011
Beiträge: 1.461

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

03.01.2014 21:34

marie m
Eroberer

Dabei seit: 08.06.2013
Beiträge: 57

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 02:53

Karlito Karlito ist männlich

Kaiser

Dabei seit: 11.04.2011
Beiträge: 1.461

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

04.01.2014 03:25

marie m
Eroberer

Dabei seit: 08.06.2013
Beiträge: 57

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

Dieser Beitrag wurde 1 mal editiert, zum letzten Mal von marie m: 05.01.2014 01:17.

05.01.2014 01:16

Karlito Karlito ist männlich

Kaiser

Dabei seit: 11.04.2011
Beiträge: 1.461

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

05.01.2014 19:04

marie m
Eroberer

Dabei seit: 08.06.2013
Beiträge: 57

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 13:27

Karlito Karlito ist männlich

Kaiser

Dabei seit: 11.04.2011
Beiträge: 1.461

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 15:53

marie m
Eroberer

Dabei seit: 08.06.2013
Beiträge: 57

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

Dieser Beitrag wurde 3 mal editiert, zum letzten Mal von marie m: 06.01.2014 16:10.

06.01.2014 16:08

Karlito Karlito ist männlich

Kaiser

Dabei seit: 11.04.2011
Beiträge: 1.461

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

06.01.2014 19:25

marie m
Eroberer

Dabei seit: 08.06.2013
Beiträge: 57

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?

Dieser Beitrag wurde 1 mal editiert, zum letzten Mal von marie m: 06.01.2014 22:16.

06.01.2014 22:16

Karlito Karlito ist männlich

Kaiser

Dabei seit: 11.04.2011
Beiträge: 1.461

Genau

06.01.2014 22:20

marie m
Eroberer

Dabei seit: 08.06.2013
Beiträge: 57

Also sind die zwei Sprachen doch nicht die selben? Oder verstehe ich es falsch?

06.01.2014 22:24

Seiten (2): [1] 2 nächste »

Baumstruktur | Brettstruktur

Informatiker Board » Themengebiete » Theoretische Informatik » Kontextfrei Sprache-Abschlusseigenschaften