TU Wien:Algebra und Diskrete Mathematik UE (diverse)/Übungen SS19/Beispiel 333

Aus VoWi
Zur Navigation springen Zur Suche springen

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

A^*, B^*, A^*B, AB^*, (A \cup B)^* und ABA^*B.

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

XY = \{w_1w_2 | w_1 \in X, w_2 \in Y\}.

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

Theorie:

Für ein Alphabet \Sigma ist \Sigma^* die Menge aller Wörter über \Sigma, d.h. x_1, x_2, \ldots, x_k \qquad \Sigma
Weiters kommt zu dieser Menge noch das leere Wort \epsilon hinzu.

Berechnung:


\begin{align}
\Longrightarrow A^* &= \lbrace \epsilon, a \rbrace \\
\Longrightarrow B^* &= \lbrace \epsilon, b, c \rbrace \\
\Longrightarrow A^*B &= \lbrace \epsilon b, \epsilon c, ab, ac \rbrace \\
\Longrightarrow AB^* &= \lbrace \epsilon a, ab, ac \rbrace \\
A \cup B &= \lbrace a, b, c  \rbrace \\
\Longrightarrow (A \cup B)^* &= \lbrace \epsilon, a, b, c \rbrace \\
AB &= \lbrace ab, ac \rbrace \\
ABA^* &= \lbrace \epsilon ab, \epsilon ac, aab, aac \rbrace \\
\Longrightarrow ABA^*B &= \lbrace \epsilon abb, \epsilon acb, \epsilon abc, \epsilon acc, aabb, aacb, aabc, aacc \rbrace
\end{align}

[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[Bearbeiten]


\begin{align}
\Longrightarrow A^* &= \lbrace \epsilon,a,aa,aaa,aaaa,... \rbrace \\
\Longrightarrow B^* &= \lbrace \epsilon,b,c,bb,bc,cb,cc,bbb,bbc,bcb,bcc,cbb,... \rbrace \\
\Longrightarrow A^*B &= \lbrace b,c,ab,ac,aab,aac,aaab,aaac,... \rbrace \\
\Longrightarrow AB^* &= \lbrace a,ab,ac,abb,abc,acc,... \rbrace \\
\Longrightarrow (A \cup B)^* &= \lbrace \epsilon,a,b,c,aa,ab,ac,ba,bb,bc,aaa,aab,... \rbrace \\
\Longrightarrow ABA^*B &= \lbrace abb,abc,acb,acc,abab,abac,acab,acac,abaab,abaac,acaab,acaac,abaaab,... \rbrace
\end{align}

Anmerkung: da \epsilon a = a und \epsilon \epsilon = \epsilon impliziert \epsilon \epsilon a = a brauchen wir \epsilon nicht jedes Mal dazuzuschreiben.