Informatiker Board | formale Sprachen | formale Sprachen L1L2=L1

Informatiker Board » Themengebiete » Theoretische Informatik » formale Sprachen » formale Sprachen L1L2=L1

» Hallo Gast [Anmelden|Registrieren]

Letzter Beitrag | Erster ungelesener Beitrag

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

formale Sprachen L1L2=L1

Autor

Beitrag

« Vorheriges Thema | Nächstes Thema »

b4shyou
Grünschnabel

Dabei seit: 15.10.2015
Beiträge: 1

formale Sprachen L1L2=L1

Zitatantwort auf diesen Beitrag erstellen

Meine Frage:
Hallo Leute, ich hänge an folgender Aufgabe:

Geben Sie zwei Sprachen L1, L2 (echte Teilmenge Alphabet*) an mit |L1|, |L2| > 1 und L1L2 = L1

Ich weiß einfach keinen Ansatz wie das denn möglich sein soll ohne, dass L2 "leere Menge" ist.
Über einen Tipp würde ich mich sehr freuen =)
LG

Meine Ideen:
siehe oben

Dieser Beitrag wurde 1 mal editiert, zum letzten Mal von b4shyou: 15.10.2015 18:54.

15.10.2015 18:52

Nehmen Sie b4shyou in Ihre Freundesliste auf

Karlito Karlito ist männlich

Kaiser

Dabei seit: 11.04.2011
Beiträge: 1.461

Hi,

du musst L1 und L2 so konstruieren, dass alle Wörter, die in L2 liegen konkateniert an alle Wörter, die in L1 liegen, keine neuen Elemente von L1 erzeugen. Nehmen wir also die Sprache, welche aus beliebig vielen konkatenierten "a" besteht. Wenn wir eine adere Sprache haben, die auch nur "a...a" enthält, so erhalten wir per Konkatenation keine neuen Elemente.

Bsp:

$[latex]<br /> L_1 & = & \{a^n ~|~ n \in \mathbb{N}\}<br /> L_2 & = & \{a,aa\}<br /> [/latex]$

Gruß,

Karlito

22.10.2015 02:29

Nehmen Sie Karlito in Ihre Freundesliste auf

Baumstruktur | Brettstruktur

Informatiker Board » Themengebiete » Theoretische Informatik » formale Sprachen » formale Sprachen L1L2=L1