Question

Let V be an alphabet, and let A and B be subsets of \({\bf{V*}}\) with A⊆B. Show that \({\bf{A*}}\)⊆B*.

Short answer

V be an alphabet, and A and B be subsets of \({\bf{V*}}\) with A⊆B then \({\bf{A*}}\)⊆\({\bf{B*}}\).

Step-by-step solution

Definition.

Here AB represents the concatenation of A and B.

\({\bf{AB = \{ xy|x}} \in {\bf{A}}\,{\bf{and}}\,{\bf{y}} \in {\bf{B\} }}\)

Kleene closure of set A consisting of the concatenation of any amount of strings from A\({{\bf{A}}^{\bf{*}}}{\bf{ = }}\bigcup\limits_{k = 0}^{ + \infty } {{{\bf{A}}^{\bf{k}}}} \)

show the result.

\({{\bf{A}}^{\bf{2}}}\) Represents the concatenation of A and A, thus

\({{\bf{A}}^{\bf{2}}}{\bf{ = AA = \{ xy|x}} \in {\bf{A}}\,{\bf{and}}\,{\bf{y}} \in {\bf{A\} }} \subseteq {\bf{\{ xy|x}} \in {\bf{Bandy}} \in {\bf{B\} = BB = }}{{\bf{B}}^{\bf{2}}}\)
Similarly, \({{\bf{A}}^{\bf{n}}}{\bf{ = (}}{{\bf{A}}^{{\bf{n - 1}}}}{\bf{)A}} \subseteq {\bf{(}}{{\bf{B}}^{{\bf{n - 1}}}}{\bf{)B}}\,{\bf{for}}\,{\bf{n = 3,4}}....\)

Using \({{\bf{A}}^{\bf{n}}} \subseteq {{\bf{B}}^{\bf{n}}}\) for n=2, 3, 4, 5...

Using the definition of the Kleene closure, then:

\({\bf{(A*) = }}\bigcup\limits_{k = 0}^{ + \infty } {{{{\bf{(A}})}^{\bf{k}}}} \subseteq \bigcup\limits_{k = 0}^{ + \infty } {{B^k}{\bf{ = }}} {{\bf{B}}^{\bf{*}}}\)

Therefore, the required result is \({\bf{A*}}\)⊆\({\bf{B*}}\).