$\Sigma = \{a, b\}$をアルファベットとする。 (1) $A = \{a, ab, abb\}, B = \{\epsilon, b\}$のとき、$AB$と$BA$を求める。 (2) $A = \{a, b\}^*, B = \{b\}$のとき、$AB$と$BA$を求める。 (3) $A = \{a, b\}^+, B = \{b\}$のとき、$AB$と$BA$を求める。 ここで、$\epsilon$は空文字列、$X^*$は$X$に属する文字列の0回以上の連接、$X^+$は$X$に属する文字列の1回以上の連接を表す。

1. 問題の内容

$\Sigma = \{a, b\}$をアルファベットとする。

(1) $A = \{a, ab, abb\}, B = \{\epsilon, b\}$のとき、$AB$と$BA$を求める。

(2) $A = \{a, b\}^*, B = \{b\}$のとき、$AB$と$BA$を求める。

(3) $A = \{a, b\}^+, B = \{b\}$のとき、$AB$と$BA$を求める。

ここで、$\epsilon$は空文字列、$X^*$は$X$に属する文字列の0回以上の連接、$X^+$は$X$に属する文字列の1回以上の連接を表す。

2. 解き方の手順

(1) $A = \{a, ab, abb\}, B = \{\epsilon, b\}$のとき

$AB = \{xy | x \in A, y \in B\}$なので、

$AB = \{a\epsilon, ab\epsilon, abb\epsilon, ab, abb, abbb\} = \{a, ab, abb, abbb\}$

$BA = \{yx | y \in B, x \in A\}$なので、

$BA = \{\epsilon a, \epsilon ab, \epsilon abb, ba, bab, babb\} = \{a, ab, abb, ba, bab, babb\}$

(2) $A = \{a, b\}^*, B = \{b\}$のとき

$AB = \{xb | x \in A\}$なので、$A$に属する任意の文字列に$b$を連接したものが$AB$となる。

つまり、$AB = \{wb | w \in \{a, b\}^*\} = \{a, b\}^*b$

$BA = \{bx | x \in A\}$なので、$A$に属する任意の文字列の先頭に$b$を連接したものが$BA$となる。

つまり、$BA = \{bw | w \in \{a, b\}^*\} = b\{a, b\}^*$

(3) $A = \{a, b\}^+, B = \{b\}$のとき

$AB = \{xb | x \in A\}$なので、$A$に属する任意の文字列に$b$を連接したものが$AB$となる。

つまり、$AB = \{wb | w \in \{a, b\}^+\} = \{a, b\}^+b$

$BA = \{bx | x \in A\}$なので、$A$に属する任意の文字列の先頭に$b$を連接したものが$BA$となる。

つまり、$BA = \{bw | w \in \{a, b\}^+\} = b\{a, b\}^+$

3. 最終的な答え

(1) $AB = \{a, ab, abb, abbb\}$

$BA = \{a, ab, abb, ba, bab, babb\}$

(2) $AB = \{a, b\}^*b$

$BA = b\{a, b\}^*$

(3) $AB = \{a, b\}^+b$

$BA = b\{a, b\}^+$