TU Wien:Algebra und Diskrete Mathematik VU (diverse)/Übungen 2025W/Beispiel 340

Für $A=\{a\}$ und $B=\{b,c\}$ bestimme man die Mengen von Wörtern

$A^{\ast }$, $B^{\ast }$, $A^{\ast }B$, $A{B}^{\ast }$, $(A\cup B{)}^{\ast }$ und $AB{A}^{\ast }B$.

Dabei gelte: Sind $X$ und $Y$ Mengen von Wörtern über einem Alphabet, dann bezeichnet

$XY=\{w_1{w}_2|w_1\in X,w_2\in Y\}$.

Dieses Beispiel hat einen unbekannten Lösungsstatus. Bitte editiere diese Seite und schreibe den dir bekannten Status ins Beispiel. Die möglichen Werte sind hier: Vorlage:Beispiel dokumentiert. Führe folgende Änderung durch:

{{Beispiel|1=
Angabetext
}}

oder

{{Beispiel|
Angabetext
}}

zu (im Falle einer korrekten, unverifizierten Lösung "solved". Auch möglich "unsolved", "wrong", "verified_by_tutor". Alle möglichen Werte sind hier: Vorlage:Beispiel dokumentiert.)

{{Beispiel|status=solved|1=
Angabetext
}}

Lösung von P.paulweber 17:48, 2. Mai 2008 (CEST)

Theorie:

Für ein Alphabet $\Sigma$ ist ${\Sigma }^{\ast }$ die Menge aller Wörter über $\Sigma$, d.h. $x_1,x_2,\dots ,x_k\Sigma$
Weiters kommt zu dieser Menge noch das leere Wort $ϵ$ hinzu.

Berechnung:

$\begin{array}{cc}⟹A^{\ast }& =\{ϵ,a\}\\ ⟹B^{\ast }& =\{ϵ,b,c\}\\ ⟹A^{\ast }B& =\{ϵb,ϵc,ab,ac\}\\ ⟹A{B}^{\ast }& =\{ϵa,ab,ac\}\\ A\cup B& =\{a,b,c\}\\ ⟹(A\cup B{)}^{\ast }& =\{ϵ,a,b,c\}\\ AB& =\{ab,ac\}\\ AB{A}^{\ast }& =\{ϵab,ϵac,aab,aac\}\\ ⟹AB{A}^{\ast }B& =\{ϵabb,ϵacb,ϵabc,ϵacc,aabb,aacb,aabc,aacc\}\end{array}$

[Anmerkung von David Mihola: Soll das der Kleene-Stern sein? Dann wäre schon A* = {E, a, aa, aaa, aaaa, ... , a^n}, etc.]

Anmerkung mick:

Diese Lösung dürfte falsch sein. Zumindest wird das auch in folgenden Foren diskutiert bzw. angesprochen.

https://web.archive.org/web/20180817162122/https://www.onlinemathe.de/forum/Eine-Menge-von-W%C3%83%C2%B6rtern-

demnach bedeutet A*, dass bei Stern beliebig viele a eingesetzt werden können oder sogar gar keins (=leeres Zeichen!)

Lösung von Damian

$\begin{array}{cc}⟹A^{\ast }& =\{ϵ,a,aa,aaa,aaaa,\mathrm{...}\}\\ ⟹B^{\ast }& =\{ϵ,b,c,bb,bc,cb,cc,bbb,bbc,bcb,bcc,cbb,\mathrm{...}\}\\ ⟹A^{\ast }B& =\{b,c,ab,ac,aab,aac,aaab,aaac,\mathrm{...}\}\\ ⟹A{B}^{\ast }& =\{a,ab,ac,abb,abc,acc,\mathrm{...}\}\\ ⟹(A\cup B{)}^{\ast }& =\{ϵ,a,b,c,aa,ab,ac,ba,bb,bc,aaa,aab,\mathrm{...}\}\\ ⟹AB{A}^{\ast }B& =\{abb,abc,acb,acc,abab,abac,acab,acac,abaab,abaac,acaab,acaac,abaaab,\mathrm{...}\}\end{array}$

Anmerkung: da $ϵa=a$ und $ϵϵ=ϵ$ impliziert $ϵϵa=a$ brauchen wir $ϵ$ nicht jedes Mal dazuzuschreiben.