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

Informatiker Board » Themengebiete » Theoretische Informatik » formale Sprachen » Für welche Sprachen gilt L1* U L2* = (L1 U L2)*

» Hallo Gast [Anmelden|Registrieren]

Letzter Beitrag | Erster ungelesener Beitrag

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

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

Autor

Beitrag

« Vorheriges Thema | Nächstes Thema »

marie m
Eroberer

Dabei seit: 08.06.2013
Beiträge: 57

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

Zitatantwort auf diesen Beitrag erstellen

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

Dieser Beitrag wurde 1 mal editiert, zum letzten Mal von marie m: 04.09.2014 23:36.

04.09.2014 23:36

Nehmen Sie marie m in Ihre Freundesliste auf

Karlito Karlito ist männlich

Kaiser

Dabei seit: 11.04.2011
Beiträge: 1.461

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

05.09.2014 14:02

Nehmen Sie Karlito in Ihre Freundesliste auf

ed209
Routinier

Dabei seit: 07.09.2006
Beiträge: 324

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?

Dieser Beitrag wurde 1 mal editiert, zum letzten Mal von ed209: 06.09.2014 11:34.

06.09.2014 11:27

Nehmen Sie ed209 in Ihre Freundesliste auf

Karlito Karlito ist männlich

Kaiser

Dabei seit: 11.04.2011
Beiträge: 1.461

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

06.09.2014 12:45

Baumstruktur | Brettstruktur

Informatiker Board » Themengebiete » Theoretische Informatik » formale Sprachen » Für welche Sprachen gilt L1* U L2* = (L1 U L2)*