Kleene-Stern Sprachen K und L. Zeige oder widerlege: K* ∩ L* ⊇ (K ∩ L)*

Question

Iteration (Kleene-Stern) einer Sprache

Ich habe hier folgende Aufgabe vor mir, die eigentlich recht simpel zu sein scheint :

Sind die folgenden Behauptungen richtig für jede Sprache K und L? Beweisen Sie die Behauptung oder widerlegen Sie durch ein Gegenbeispiel.

a)K* ∩ L* ⊇ (K ∩ L)*

Also die linke Seite soll eine Obermenge der rechten Seite sein. Mein Problem ist, dass ich mit Mengenlehre unter anderem noch nicht richtig vertraut bin, vor allem was die ganzen Formalitäten angeht, da ich als Quereinsteiger ins Sommersemester begonnen habe.

Der Stern beschreibt ja einfach die Menge aller Wörter, die durch beliebige Verknüpfungen von Wörtern der gegebenen Sprache gebildet werden können.

Mein Ansatz war jetzt einfach zu bestimmen, dass beispielweise w ein Element aus (K ∩ L)* ist und w halt w=w1,...,wn. Ich habe einfach keine Ahnung wie ich das alles formal aufschreiben muss, um es am Ende einen gültigen Beweis nennen zu können. Ich muss einmal sehen, wie es funktioniert, um es anwenden zu können. Könnte mir da jemand helfen?

Answer 1

Es ist K ∩ L ⊆ K. Also ist (K ∩ L)* ⊆ K*

Es ist K ∩ L ⊆ L. Also ist (K ∩ L)* ⊆ L*

Weil (K ∩ L)* ⊆ K* und (K ∩ L)* ⊆ L* sind, ist auch (K ∩ L)* ⊆ K* ∩ L*

Comments

Wie wäre es denn für die umgekehrte Aussage?

K* ∩ L* ⊆ (K ∩ L)*

K* ⊆ (K ∩ L)*

L* ⊆ (K ∩ L)*

Funktioniert ja hier so nicht, da würde ich eher sagen, dass es keine Teilmenge ist.

Ist die Aussage K* ∩ L* ⊆ (K ∩ L)* denn überhaupt wahr, oder ist diese sogar zu widerlegen?

---

Sei w ∈ K* ∩ L*. Dann ist w ∈ K*. Also sind alle Buchtaben von w in K.

Es ist auch w ∈ L*. Also sind alle Buchtaben von w in L.

Somit besteht w nur aus Buchstaben, die in K ∩ L sind.