Question

Prove or disprove each of these statements for subsets \({\bf{A}}\), \({\bf{B}}\), and \({\bf{C}}\) of \({{\bf{V}}^{\bf{*}}}\), where \({\bf{V}}\) is an alphabet.

\({\bf{a)}}\)\({\bf{A(B}} \cup {\bf{C) = AB}} \cup {\bf{AC}}\)

\({\bf{b)}}\)\({\bf{A(B}} \cap {\bf{C) = AB}} \cap {\bf{AC}}\)

\({\bf{c)}}\)\(\left( {{\bf{A B}}} \right){\bf{ C = A}}\left( {{\bf{B C}}} \right)\)

\({\bf{d)}}\)\({\bf{(A}} \cup {\bf{B) = A}} \cup {{\bf{B}}^{\bf{*}}}\)

Short answer

\({\bf{a)}}\)The given \({\bf{A(B}} \cup {\bf{C) = AB}} \cup {\bf{AC}}\) is proved.

\({\bf{b)}}\)The given \({\bf{A(B}} \cap {\bf{C) = AB}} \cap {\bf{AC}}\) is proved.

\({\bf{c)}}\)The given \(\left( {{\bf{A B}}} \right){\bf{ C = A}}\left( {{\bf{B C}}} \right)\) is proved.

\({\bf{d)}}\) The given \({{\bf{(A}} \cup {\bf{B)}}^{\bf{*}}} \ne {{\bf{A}}^{\bf{*}}} \cup {{\bf{B}}^{\bf{*}}}\) is disproved.

Step-by-step solution

Definition

Kleene closure of \({\bf{A}}\) : Set consisting of concatenations of any number of strings from \({\bf{A}}\)

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

Union \({\bf{A}} \cup {\bf{B}}\) : All elements that are either in in \({\bf{B}}\) (or both).

Intersection \({\bf{A}} \cap {\bf{B}}\) : All elements that are both in \({\bf{A}}\) AND in \({\bf{B}}\).

Distributive laws

\(\begin{array}{l}{\bf{x}} \vee {\bf{(y}} \wedge {\bf{z) = (x}} \vee {\bf{y)}} \wedge {\bf{(x}} \vee {\bf{z)}}\\{\bf{x}} \wedge {\bf{(y}} \vee {\bf{z) = (x}} \wedge {\bf{y)}} \vee {\bf{(x}} \wedge {\bf{z)}}\end{array}\)

Idempotent law:

\(\begin{array}{l}{\bf{A}} \cup {\bf{A = A}}\\{\bf{A}} \cap {\bf{A = A}}\end{array}\)

Commutative laws:

\({\bf{A}} \cup {\bf{B = B}} \cup {\bf{A}}\)and \({\bf{A}} \cap {\bf{B = B}} \cap {\bf{A}}\)

Associative laws:

\({\bf{(A}} \cup {\bf{B)}} \cup {\bf{C = A}} \cup {\bf{(B}} \cup {\bf{C)}}\)and \({\bf{(A}} \cap {\bf{B)}} \cap {\bf{C = A}} \cap {\bf{(B}} \cap {\bf{C)}}\)

Prove or disprove the given statement

(a)

Given: \({\bf{A,B,C}} \subseteq {{\bf{V}}^{\bf{*}}}\)

Where \({\bf{V}}\) is an alphabet.

To proof: \({\bf{A(B}} \cup {\bf{C) = AB}} \cup {\bf{AC}}\)

PROOF

Use distributive law

\(\begin{aligned} A(B \cup C) &= \{ ab\mid a \in A \wedge b \in B \cup C\} \\ & = \{ ab\mid a \in A \wedge (b \in B \vee b \in C)\} \\ &= \{ ab\mid (a \in A \wedge b \in B) \vee (a \in A \wedge b \in C)\} \\ &= \{ ab\mid (a \in A \wedge b \in B) \vee (a \in A \wedge b \in C)\} \\ &= \{ ab\mid (a \in A \wedge b \in B)\} \cup \{ ab\mid (a \in A \wedge b \in C)\} \\ & = AB \cup AC \\ \end{aligned}\)

Therefore, the given \({\bf{A(B}} \cup {\bf{C) = AB}} \cup {\bf{AC}}\) is proved.

Prove or disprove the given statement

(b)

Given: \({\bf{A,B,C}} \subseteq {{\bf{V}}^{\bf{*}}}\)

Where \({\bf{V}}\) is an alphabet.

To proof: \({\bf{A(B}} \cap {\bf{C) = AB}} \cap {\bf{AC}}\)

PROOF

Use associative, idempotent and commutative law

\(\begin{aligned} A(B \cap C) &= \{ ab\mid a \in A \wedge b \in B \cap C\} \\ &= \{ ab\mid a \in A \wedge (b \in B \wedge b \in C)\} \\ &= \{ ab\mid (a \in A \wedge a \in A) \wedge (b \in B \wedge b \in C)\} \\ &= \{ ab\mid a \in A \wedge (a \in A \wedge (b \in B \wedge b \in C))\} \\ \end{aligned} \)

Further, solve the above expression,

\(\begin{aligned} A(B \cap C) &= \{ ab\mid a \in A \wedge ((a \in A \wedge b \in B) \wedge b \in C)\} \\ &= \{ ab\mid a \in A \wedge ((b \in B \wedge a \in A) \wedge b \in C)\} \\ & = \{ ab\mid a \in A \wedge (b \in B \wedge (a \in A \wedge b \in C))\} \\ & = \{ ab\mid (a \in A \wedge b \in B) \wedge (a \in A \wedge b \in C)\} \\ & = \{ ab\mid (a \in A \wedge b \in B)\} \cap \{ ab\mid (a \in A \wedge b \in C)\} \\ & = AB \cap AC \\\end{aligned} \)

Therefore, the given \({\bf{A(B}} \cap {\bf{C) = AB}} \cap {\bf{AC}}\) is proved.

Prove or disprove the given statement

(c)

Given: \({\bf{A,B,C}} \subseteq {{\bf{V}}^{\bf{*}}}\)

Where \({\bf{V}}\) is an alphabet.

To proof: \(\left( {{\bf{A B}}} \right){\bf{ C = A}}\left( {{\bf{B C}}} \right)\)

PROOF

Use associative law

\(\begin{aligned} (AB)C &= \{ xc\mid a \in AB \wedge c \in C\} \\ & = \{ abc\mid (a \in A \wedge b \in B) \wedge c \in C\} \\ &= \{ abc\mid a \in A \wedge (b \in B \wedge c \in C)\} \\ &= \{ ay\mid a \in A \wedge y \in BC\} \\ &= A(BC) \\ \end{aligned} \)

Therefore, the given \(\left( {{\bf{A B}}} \right){\bf{ C = A}}\left( {{\bf{B C}}} \right)\) is proved.

Prove or disprove the given statement

(d)

The statement \({{\bf{(A}} \cup {\bf{B)}}^{\bf{*}}}{\bf{ = }}{{\bf{A}}^{\bf{*}}} \cup {{\bf{B}}^{\bf{*}}}\) is false, with you will justify with a counter example.

Counter example:

Let \({\bf{A = }}\left\{ {\bf{0}} \right\}\) and \({\bf{B = }}\left\{ {\bf{1}} \right\}\). Then note \({\bf{A}} \cup {\bf{B = \{ 0,1\} }}\).

\({{\bf{A}}^{\bf{*}}}\)contains strings with only \({\bf{0's}}\) and \({{\bf{B}}^{\bf{*}}}\) contains only strings of \({\bf{1's}}\). Note that \({{\bf{A}}^{\bf{*}}} \cup {{\bf{B}}^{\bf{*}}}\) contains all bit strings that contain only \({\bf{1's}}\) or only \({\bf{0's}}\), while \({{\bf{(A}} \cup {\bf{B)}}^{\bf{*}}}\) contains all possible bit strings. Thus, it is not the same set.

For example, \(10 \notin {{\bf{A}}^{\bf{*}}} \cup {{\bf{B}}^{\bf{*}}}\)and \(10 \in {{\bf{(A}} \cup {\bf{B)}}^{\bf{*}}}\) as \(10\) is a bit string that does not contain only \({\bf{0's}}\) nor only \({\bf{1's}}\).

Therefore, the given \({{\bf{(A}} \cup {\bf{B)}}^{\bf{*}}} \ne {{\bf{A}}^{\bf{*}}} \cup {{\bf{B}}^{\bf{*}}}\) is disproved.