Question

Suppose that A is a subset of\({{\bf{V}}^{\bf{*}}}\)where V is an alphabet.Prove or disprove each of these statements.

\(\begin{array}{l}{\bf{a)}}\,\,{\bf{A}} \subseteq {{\bf{A}}^{\bf{2}}}\\{\bf{b)}}\,\,{\bf{if}}\,{\bf{A = }}{{\bf{A}}^{\bf{2}}}{\bf{,then}}\,{\bf{\lambda }} \in {\bf{A}}\\{\bf{c)}}\,\,{\bf{A\{ \lambda \} = A}}\\{\bf{d)}}\,\,{{\bf{(}}{{\bf{A}}^{\bf{*}}}{\bf{)}}^{\bf{*}}}{\bf{ = }}{{\bf{A}}^{\bf{*}}}\\{\bf{e)}}\,\,{{\bf{A}}^{\bf{*}}}{\bf{A = }}{{\bf{A}}^{\bf{*}}}\\{\bf{f)}}\,\,\left| {{{\bf{A}}^{\bf{n}}}} \right|{\bf{ = }}{\left| {\bf{A}} \right|^{\bf{n}}}\end{array}\)

Short answer

1. The statement is false.
2. The statement is false.
3. The statement is true
4. The statement is true.
5. The statement is false.
6. The statement is false.

Step-by-step solution

Definition

Here AB represents the concatenation of A and B.

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

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

Show the result for \({\bf{A}} \subseteq {{\bf{A}}^{\bf{2}}}\).

(a)Here it is given \(A \subseteq {A^2}\).

\(A \subseteq {A^2}\)is not always true.

It proved it by an example. - if \(A = \left\{ {10} \right\}\), then

\(\begin{aligned}{A^2} &= AA\\ &= \left\{ {xy|x \in A\,{\rm{and}}\,y \in A} \right\}\\ &= \left\{ {xy|x \in 10\,{\rm{and}}\,y \in 10} \right\}\\ &= \left\{ {1010} \right\}\end{aligned}\)

Since,\({A^2}\)does not contain 10.

Hence, the statement is false.

Find the result \({\bf{if}}\,{\bf{A = }}{{\bf{A}}^{\bf{2}}}{\bf{,then}}\,{\bf{\lambda }} \in {\bf{A}}\).

(b)If \(A = {A^2},\,\,{\rm{then}}\,\lambda \in A\)

The statement is not true if \(A = \phi \) because \(A = {A^2}\)is true while\(\lambda \notin A\).

\(\begin{aligned}{c}{A^2} &= \phi \phi \\ &= \left\{ {xy|x \in \phi \,and\,y \in \phi } \right\}\\ &= \phi \\ &= A\\{A^2} &= A\end{aligned}\)

Get the result for \({\bf{A\{ \lambda \}  = A}}\).

(c)\(\begin{aligned}A\left( \lambda \right) &= \left\{ {xy|x \in A\,{\rm{and}}\,y \in \left\{ \lambda \right\}} \right\}\\ &= \left\{ {xy|x \in A\,{\rm{and}}\,y \in \lambda } \right\}\\ &= \left\{ {x\lambda |x \in A} \right\}\\ &= \left\{ {x|x \in A} \right\}\\A\left( \lambda \right) &= A\end{aligned}\)

Proof of \({{\bf{(}}{{\bf{A}}^{\bf{*}}}{\bf{)}}^{\bf{*}}}{\bf{ = }}{{\bf{A}}^{\bf{*}}}\).

(d)Now, according to the Kleene closure's definition

\({\left( {{A^*}} \right)^*} = \bigcup\limits_{k = 0}^{ + \infty } {{{\left( {{A^*}} \right)}^k}} \)

\({\left( {{A^*}} \right)^2}\)Represent the concatenation of\({A^*}\)and\({A^*}\) Thus

\(\begin{aligned}{c}{\left( {{A^*}} \right)^2} &= \left\{ {xy|x \in A\,{\rm{and}}\,y \in {A^*}} \right\}\\{\left( {{A^*}} \right)^2} &= {A^*}\end{aligned}\)

Similarly,

\(\begin{aligned}{\left( {{A^*}} \right)^n} &= {\left( {{A^*}} \right)^{n - 1}}{A^*}\\ &= {A^*}{A^*}\\ &= {\left( {{A^*}} \right)^2}\\ &= {A^*}form\\ &= 2,3,...\end{aligned}\)

Using the definition of the Kleene closure, then

\(\begin{aligned}{c}\left( {A*} \right)* &= \bigcup\limits_{k = 0}^{ + \infty } {{{\left( {{A^*}} \right)}^k}} \\ &= \bigcup\limits_{k = 0}^{ + \infty } {\left( {{A^*}} \right)} A*\end{aligned}\)

Similarly,

\(\begin{aligned}{c}{\left( {A*} \right)^{^n}} &= {\left( {A*} \right)^{^{n - 1}}}A*\\ &= A*A*\\ &= {\left( {A*} \right)^2}\\ &= A*\end{aligned}\)

Using the definition of the Kleene closure, then

\(\begin{aligned}{c}\left( {A*} \right)* &= \bigcup\limits_{k = 0}^{ + \infty } {{{\left( {{A^*}} \right)}^k}} \\ &= \bigcup\limits_{k = 0}^{ + \infty } {\left( {{A^*}} \right)} \\\left( {A*} \right)* &= A*\end{aligned}\)

find the result for \({{\bf{A}}^{\bf{*}}}{\bf{A = }}{{\bf{A}}^{\bf{*}}}\).

(e)\(A*A = A*\)is not true if \(\lambda \notin A\),because contains\(\lambda \) and\(A*A\) will not contains\(\lambda \) (since A does not contains \(\lambda \)).

Show result \(\left| {{{\bf{A}}^{\bf{n}}}} \right|{\bf{ = }}{\left| {\bf{A}} \right|^{\bf{n}}}\).

(f)The result show by the example.

Let \({\bf{A = \{ \lambda ,1\} }}\)

X	Y	xy
\(\lambda \)	\(\lambda \)	\(\lambda \)
\(\lambda \)	1	1
1	\(\lambda \)	1
1	1	11

Then\({A^2} = \left\{ {xy|x \in A\,{\rm{and}}\,y \in A} \right\} = \left\{ {\lambda ,1,11} \right\}\). Since A contains 2 elements and \({A^2}\)contains 3 elements.

Thus, the statement is false.