Informatiker Board | Druckvorschau: formale Sprachen L1L2=L1

Informatiker Board (http://www.informatikerboard.de/board/index.php)
- Themengebiete (http://www.informatikerboard.de/board/board.php?boardid=1)
--- Theoretische Informatik (http://www.informatikerboard.de/board/board.php?boardid=5)
---- formale Sprachen (http://www.informatikerboard.de/board/board.php?boardid=12)
----- formale Sprachen L1L2=L1 (http://www.informatikerboard.de/board/thread.php?threadid=2481)

Geschrieben von b4shyou am 15.10.2015 um 18:52:

formale Sprachen L1L2=L1

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

Geschrieben von Karlito am 22.10.2015 um 02:29:

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