Reguläre Sprachen Informatik

Question

Hallo,

ich mace gerade eine Übung für die Uni und komme bei einer Teilaufgabe nicht weiter. Ich hoffe hier kann man mir helfen:

Aufgabe:

Für L ⊆ Σ*  ist L* die kleinste Sprache, welche L umfasst, ε enthält und unter der Konkatenation ◦ abgeschlossen sit. 

Nun soll ich folgendes zeigen :

∀L′ | L ⊆ L′ ∧ ε ∈ L′ ∧ L′ ◦L′ ⊆ L′ gilt L∗ ⊆ L′. Erläuterung: Die Sprache L′ soll hier als Hilfestellung (“größere” Sprache) verwendet werden, um in der nächsten Teilaufgabe zu zeigen, dass L*  die kleinste Sprache sein muss.

Ich galube ich kann das hier induktiv zeigen also über n von L^(n) aber ich weiß nicht mehr weiter wie ich das überhaupt angehen soll. Wäre über eine Hilfe sehr dankbar.

LG

Answer 1

Für L ⊆ Σ*  ist L* die kleinste Sprache, welche L umfasst, ε enthält und unter der Konkatenation ◦ abgeschlossen sit. 

Ich ignoriere das mal und fasse * als den Kleene-Stern auf. Es ergibt keinen Sinn, L* so zu definieren, wenn nicht klar ist, was mit kleinste Sprache gemeint ist.

Sei L' derart, dass L ⊆ L′ ∧ ε ∈ L′ ∧ L′ ◦L′ ⊆ L′ ist.

Sei w ∈ L*.

Ist w = ε, dann ist w ∈ L' laut Definition von L'.

Ist w ≠ ε, dann seien w₁,..., w_n ∈ L, so dass w = w₁◦...◦w_n ist.

IA: Es ist w₁ ∈ L' laut Definition von L'.

IV: Sei 1 < i < n und w₁◦...◦w_i ∈ L' .

IS: Zeige, dass w₁◦...◦w_i+1 ∈ L' ist.