Informatiker Board | Druckvorschau: Für welche Sprachen gilt L1* U L2* = (L1 U L2)*

Geschrieben von marie m am 04.09.2014 um 23:36:

Für welche Sprachen gilt L1* U L2* = (L1 U L2)*

Hallo!!!

Für welche Sprachen [latex]L_1[/latex]

und

, die keine Untergruppe voneinander sind, gilt es
$[latex]L_1^* \cup L_2^* = \left(L_1 \cup L_2\right)^*[/latex]$ ?

Geschrieben von Karlito am 05.09.2014 um 14:02:

Hallo marie,

ich habe nicht lange darüber nachgedacht, aber bisher fällt mir nur folgendes ein:

Eine Sprache beliebig (nur leeres Wort darf nicht enthalten sein), die andere Sprache enthält nur das leere Wort.
Eine Sprache beliebig, die andere Sprache ist die leere Sprache (enthält kein Wort)

Edit: Mein Lösungsweg: Wenn man die eine Sprache mit der anderen Vereinigt und darüber den Stern bildet, so dürfen die Elemente der anderen Sprache mittels der Konkatenation zu keinen neuen Wörtern führen. Wir suchen also eine Art neutrales Element. Das ist mit Epsilon gegeben. Bei der leeren Sprache habe ich mich leider geirrt, da die leere Sprache ja Teilmenge jeder anderen Sprache ist.

Bitte noch mal kritisch darüber nachdenken.

Gruß,

Karlito

Geschrieben von ed209 am 06.09.2014 um 11:27:

Ich weiss jetzt nicht was Untergruppe bedeutet, aber ist die Leere Menge nicht gerade eine Teilmenge?

So wie die Frage gestellt ist, klingt es als sei zu beweisen daß es das keine zwei Sprachen gibt für die das zutrifft.

Gruß,
ED

PS: Ne, wie ich die Frage verstanden habe. Habe ich eine beliebige Vielzahl von Sprachpaaren gefunden, auf die das zutrifft. Insofern find ich die Fragestellung komisch. Wonach genau ist gesucht und woher kommt die Frage?

Geschrieben von Karlito am 06.09.2014 um 12:45:

Hallo,

ja, stimmt, der Gruppenbegriff kann hier nicht wirklich angewendet werden, da es bei den angewendeten binären Operatoren (Konkatenation und Vereinigung) kein Inverses Element gibt, oder? Ich nehme daher an, dass Teilmenge gemeint ist.

Gruß,

Karlito