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(\alpha )$ and $B=L(\beta )$. The semantics of regular expressions reduce the claim towhere juxtaposition is concatenation of formal languages and a star is the Kleene star.

Every element of $A^{\ast }{B}^{\ast }$ is a finite concatenation of members of $A\cup B$, so belongs to $(A\cup B{)}^{\ast }$. Concatenating any finite number of such elements still belongs to $(A\cup B{)}^{\ast }$, proving $(A^{\ast }{B}^{\ast }{)}^{\ast }\subseteq (A\cup B{)}^{\ast }$.

Conversely, $A\subseteq A^{\ast }{B}^{\ast }$ because one may take a single member of $A$ followed by the empty string from $B^{\ast }$. Likewise $B\subseteq A^{\ast }{B}^{\ast }$ by taking the empty string from $A^{\ast }$. Hence any finite concatenation of members of $A\cup B$ lies in $(A^{\ast }{B}^{\ast }{)}^{\ast }$. The empty string belongs to both sides. Thus