Beweis der Eigenschaft $L^{*} \subseteq L$

Gegeben sei das Alphabet $Σ = {a, b, c}$ und die Sprache $L$ definiert als:

L = {w \in Σ^{*} ∣ #_{a} (w) + #_{b} (w) = #_{c} (w)}

Die Sprache $L$ besteht also aus allen Wörtern über $Σ$ , in denen die Summe der Anzahlen der Buchstaben ‘a’ und ‘b’ gleich der Anzahl der Buchstaben ‘c’ ist.

Zu zeigen (Z.Z.): $L^{*} \subseteq L$

Beweis:

Wir nehmen zwei beliebige Wörter $w_{1}, w_{2} \in L$ . Nach Definition von $L$ gilt:
$#_{a} (w_{1}) + #_{b} (w_{1}) = #_{c} (w_{1})$
und
$#_{a} (w_{2}) + #_{b} (w_{2}) = #_{c} (w_{2})$
Betrachten wir das Wort $w = w_{1} w_{2}$ , die Konkatenation von $w_{1}$ und $w_{2}$ . Es gilt für die Anzahlen der Buchstaben in $w$ :
$#_{a} (w) = #_{a} (w_{1}) + #_{a} (w_{2})$ $#_{b} (w) = #_{b} (w_{1}) + #_{b} (w_{2})$ $#_{c} (w) = #_{c} (w_{1}) + #_{c} (w_{2})$
Durch Addition der entsprechenden Gleichungen für $w_{1}$ und $w_{2}$ erhalten wir:
$#_{a} (w) + #_{b} (w) = (#_{a} (w_{1}) + #_{b} (w_{1})) + (#_{a} (w_{2}) + #_{b} (w_{2}))$
Da $#_{a} (w_{1}) + #_{b} (w_{1}) = #_{c} (w_{1})$ und $#_{a} (w_{2}) + #_{b} (w_{2}) = #_{c} (w_{2})$ , kann dies umgeschrieben werden zu:
$#_{a} (w) + #_{b} (w) = #_{c} (w_{1}) + #_{c} (w_{2})$
Dies entspricht der Anzahl der ‘c’s in $w$ :
$#_{a} (w) + #_{b} (w) = #_{c} (w)$
Also erfüllt jedes Wort $w$ , das durch Konkatenation von Wörtern aus $L$ gebildet wird, die Bedingung für die Zugehörigkeit zu $L$ . Daher ist jedes Wort in $L^{*}$ auch in $L$ enthalten.
Zusätzlich ist das leere Wort $ϵ$ , das durch die Anwendung des Kleene-Sterns eingeschlossen ist, trivialerweise in $L$ , da keine Buchstaben vorhanden sind und somit die Bedingung $#_{a} (ϵ) + #_{b} (ϵ) = #_{c} (ϵ)$ erfüllt ist, da alle Zählungen null sind.

Fazit:

Da sowohl das leere Wort als auch jede Konkatenation von Wörtern aus $L$ die definierende Eigenschaft von $L$ erfüllen, haben wir gezeigt, dass $L^{*} \subseteq L$ .

🎓 MyUniNotes

Explorer

Induktiver Beweis für FSK1-1d

Beweis der Eigenschaft $L^{*} \subseteq L$

Graph View

Backlinks

🎓 MyUniNotes

Explorer

Induktiver Beweis für FSK1-1d

Beweis der Eigenschaft L∗⊆L

Graph View

Backlinks

Beweis der Eigenschaft $L^{*} \subseteq L$