Question

Determine whether the string 01001 is in each of these sets.

a){0,1}* b){0}*{10}{1}*

c){010}*{0}*{1} d){010,011} {00,01}

e){00} {0}*{01} f){01}*{01}*

Short answer

1. The string contains 01001.
2. The string does not contain 01101.
3. It contains string 01101.
4. It contains string 01101.
5. It does no t contain string 01101.
6. It does not contain string 01101.

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 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 result of {0, 1}*

By the definition of Kleene closure and the concatenation, \({{\bf{\{ 0,1\} }}^{\bf{*}}}\)contains any sequence of 0’s and 1’s.

Thus it also contains the bit string {01101}.

show the result of {0}*{10}{1}*

By the definition of Kleene closure and concatenation, \({{\bf{\{ 1\} }}^{\bf{*}}}\)contains any sequence of 0’s and \({{\bf{\{ }}0{\bf{\} }}^{\bf{*}}}\) contains a sequence of 0’s.

{0}*{10}{1}*then contains a string sequence of 0’s, 10, and 1’s respectively.

This implies that{0}*{10}{1}* does not contains the bit string {01001}.

Find the result of {010}*{0}*{1}

By the definition of Kleene closure and the concatenation,\({{\bf{\{ }}0{\bf{\} }}^{\bf{*}}}\) contains a sequence of 010’s and \({{\bf{\{ }}0{\bf{\} }}^{\bf{*}}}\) contains a sequence of 0’s.

{010}*{0}*{1}contains a string with sequence 010, followed by any sequence of zeros, followed by 1.

This implies that {010}*{0}*{1} contains bit strings 01001, since starts with 010, followed by 0, then 1.

Get the result of {010, 011} {00, 01}

{010,011}{00, 01} represents the concatenation of {010, 011}

\(X\)	\(Y\)	\(XY\)
010	00	01000
010	01	01001
011	00	01100
011	01	01101

This contains the string {01001}.

Solve for {00} {0}*{01}

By the definition of Kleene closure and concatenation, \({{\bf{\{ 0\} }}^{\bf{*}}}\) contains any sequence of 0.

{00} {0}*{01}then contains a string with two 0’s, then 0’s and ends with 01.

This implies that{00} {0}*{01} does notcontains the bit string 00101, since 00101 contains multiple of 1’s and a string in {00} {0}*{01} can contain only ones 1.

Find the result for {01}*{01}* 

By the definition of Kleene closure and the concatenation, \({{\bf{\{ 0}}1{\bf{\} }}^{\bf{*}}}\) contains any sequence of 01’s.

{01}*{01}*then contains a string with two 01’s.

This implies that){01}*{01}* does notcontains the bit string 00101, since 01101 does not contain the same number of zeros and ones.

Therefore, the required results are:

1. The string contains 01001.
2. The string does not contain 01101.
3. It contains string 01101.
4. It contains string 01101.
5. It does not contain string 01101.
6. It does not contain string 01101.