0 Daumen
574 Aufrufe

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

Avatar von

1 Antwort

+1 Daumen
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 w1,..., wn ∈ L, so dass w = w1◦...◦wn ist.

IA: Es ist w1 ∈ L' laut Definition von L'.

IV: Sei 1 < i < n und w1◦...◦wi ∈ L' .

IS: Zeige, dass w1◦...◦wi+1 ∈ L' ist.

Avatar von 5,6 k

Ein anderes Problem?

Stell deine Frage

Willkommen bei der Stacklounge! Stell deine Frage einfach und kostenlos

x
Made by a lovely community