 Solution

ID: past-exam-of-the-year-1-of-the-computer-science-course-of-the-university-of-oxford/2003/calculus-probability-linear-algebra-discrete-mathematics-logic-and-proof-and-models-of-computation/9/d/solution

The assertion is true. Write

A = L (α)

and

B = L (β)

. The semantics of regular expressions reduce the claim to

(A^{*} B^{*})^{*} = (A \cup B)^{*},

Every element of

A^{*} B^{*}

is a finite concatenation of members of

A \cup B

, so belongs to

(A \cup B)^{*}

. Concatenating any finite number of such elements still belongs to

(A \cup B)^{*}

, proving

(A^{*} B^{*})^{*} \subseteq (A \cup B)^{*}

Conversely,

A \subseteq A^{*} B^{*}

because one may take a single member of

A

followed by the empty string from

B^{*}

. Likewise

B \subseteq A^{*} B^{*}

by taking the empty string from

A^{*}

. Hence any finite concatenation of members of

A \cup B

lies in

(A^{*} B^{*})^{*}

. The empty string belongs to both sides. Thus

L ((α^{*} β^{*})^{*}) = L ((α + β)^{*}) .

 New to topics? Read the docs here!