Question

Describe the elements of the set \({{\bf{A}}^{\bf{*}}}\)for these values of A.

a){10}b){111}c){0, 01}d){1,101}

Short answer

1. \({\bf{(A*) = \{ 1}}{{\bf{0}}^{\bf{k}}}{\bf{\} ,k = 0,1,2}}...{\bf{\} }}\).
2. \({\bf{(A*) = \{ 11}}{{\bf{1}}^{\bf{k}}}{\bf{\} |k = 0,1,2}}...{\bf{\} }}\).
3. \({\bf{A*}}\)=Set of bit strings where 1 always immediately precedes a 0.
4. \({\bf{A*}}\)= set of bit strings with at least two 1s between consecutive 0s.

Step-by-step solution

Definition.

Here AB represents the concatenation of A and B.

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

Kleene closure of a 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}}}} \)

Find the result for {10}

Here A= {10}.

By the definition of concatenation

\(\begin{array}{c}{{\bf{A}}^{\bf{2}}}{\bf{ = AA = \{ 1010\} }}\\{{\bf{A}}^{\bf{3}}}{\bf{ = }}{{\bf{A}}^{\bf{2}}}{\bf{A = \{ 101010\} }}\\{\bf{.}}\\{\bf{.}}\\{{\bf{A}}^{\bf{k}}}{\bf{ = (}}{{\bf{A}}^{{\bf{k - 1}}}}{\bf{)A = (1}}{{\bf{0}}^{{\bf{k - 1}}}}{\bf{)(10) = \{ 1}}{{\bf{0}}^{\bf{k}}}{\bf{\} }}\end{array}\)

Using the definition of the Kleene closure, then

\({\bf{(A*) = }}\bigcup\limits_{k = 0}^{ + \infty } {{{{\bf{(A}})}^{\bf{k}}}} = \bigcup\limits_{k = 0}^{ + \infty } {{{\{ 10\} }^k} = } {\bf{\{ 1}}{{\bf{0}}^{\bf{k}}}{\bf{\} ,k = 0,1,2}}...{\bf{\} }}\)

Determine the result of {111}

Here \({\bf{A = }}\left\{ {{\bf{111}}} \right\}\)

By the definition of concatenation

\(\begin{array}{c}{{\bf{A}}^{\bf{2}}}{\bf{ = AA = \{ 111111\} = \{ (111}}{{\bf{)}}^{\bf{2}}}{\bf{\} }}\\{{\bf{A}}^{\bf{3}}}{\bf{ = }}{{\bf{A}}^{\bf{2}}}{\bf{A = \{ 111111111\} = \{ (111}}{{\bf{)}}^{\bf{3}}}{\bf{\} }}\\{\bf{.}}\\{\bf{.}}\\{{\bf{A}}^{\bf{k}}}{\bf{ = (}}{{\bf{A}}^{{\bf{k - 1}}}}{\bf{)A = (11}}{{\bf{1}}^{{\bf{k - 1}}}}{\bf{)(111) = \{ 11}}{{\bf{1}}^{\bf{k}}}{\bf{\} }}\end{array}\)

Using the definition of the Kleene closure, then:

\({\bf{(A*) = }}\bigcup\limits_{k = 0}^{ + \infty } {{{{\bf{(A}})}^{\bf{k}}}} = \bigcup\limits_{k = 0}^{ + \infty } {{{\{ 111\} }^k} = } {\bf{\{ 1}}{11^{\bf{k}}}{\bf{\} }}|{\bf{k = 0,1,2}}...{\bf{\} }}\)

Solve for the {0,01}

Here \({\bf{A = }}\left\{ {{\bf{0, 01}}} \right\}\)

By the definition of concatenation

\(\begin{array}{c}{{\bf{A}}^{\bf{2}}}{\bf{ = AA = \{ 00,001,010,0101\} }}\\{{\bf{A}}^{\bf{3}}}{\bf{ = }}{{\bf{A}}^{\bf{2}}}{\bf{A = \{ 000,0001,0010,00101,0010,0110,0001,00101,010101\} }}\end{array}\)

Using the definition of the Kleene closure, then:

\({\bf{A*}}\)=Set of bit strings where 1 always immediately proceeds a 0.

Find the result for {1,101}

Here \({\bf{A = }}\left\{ {{\bf{1, 101}}} \right\}\)

By the definition of concatenation

\(\begin{array}{l}{{\bf{A}}^{\bf{2}}}{\bf{ = AA = \{ 1101,1011,101101\} }}\\{{\bf{A}}^{\bf{3}}}{\bf{ = }}{{\bf{A}}^{\bf{2}}}{\bf{A = \{ 11101,11011,10111,1101101,1011011,1011101,101101101\} }}\end{array}\)

Using the definition of the Kleene closure, then:

\({\bf{A*}}\)= A set of bit strings with at least two 1s between consecutive 0s.

Therefore,

1. \({\bf{(A*) = \{ 1}}{{\bf{0}}^{\bf{k}}}{\bf{\} ,k = 0,1,2}}...{\bf{\} }}\).
2. \({\bf{(A*) = \{ 11}}{{\bf{1}}^{\bf{k}}}{\bf{\} |k = 0,1,2}}...{\bf{\} }}\).
3. \({\bf{A*}}\)=Set of bit strings where 1 always immediately precedes a 0.
4. \({\bf{A*}}\)= set of bit strings with at least two 1s between consecutive 0s.