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

The assertion is true. Every single finite string $w=b_1\cdots b_k$ over $\{0,1\}$ is denoted by the regular expression $b_1\cdots b_k$. The empty string is denoted by $ϵ$. Hence if $F=\{w_1,\dots ,w_m\}$ is a finite formal language, the regular expressiondenotes precisely $F$, with each $w_j$ read as its concatenation of symbols. This uses the defining union and concatenation operations for regular expressions. For $F=\varnothing$, use the regular expression $\varnothing$. Therefore

The assertion is false. Use the pumping lemma for regular languages: if $L$ is a regular language, there is $p\ge 1$ such that every $w\in L$ with $|w|\ge p$ admits a factorization $w=xyz$ with $|xy|\le p$, $|y|\ge 1$, and $x{y}^{k}z\in L$ for every integer $k\ge 0$.

Suppose the stated formal language were a regular language, and take $w=0^{2p}{1}^p$. This string has twice as many zeros as ones, so it belongs to $L$. In every allowed factorization, the first $p$ positions are all zeros, forcing $y=0^d$ with $1\le d\le p$. Pumping down with $k=0$ producesIt still has $p$ ones but fewer than $2p$ zeros, contradicting the pumping lemma for regular languages. Thus

The assertion is false. Suppose the formal language $L=\{ww:w\in \{0,1{\}}^{\ast }\}$ were a regular language, and let $p$ be its constant from the pumping lemma for regular languages. ConsiderIn every decomposition $t=xyz$ with $|xy|\le p$ and $|y|\ge 1$, the pumped factor is $y=0^d$ with $1\le d\le p$. Pumping down givesThis string has exactly two ones and ends in a one. If it were $vv$, each copy of $v$ would contain exactly one one, and each copy would end in a one. The first copy would consequently be $0^{p-d}1$, while the second would be $0^{p}1$. They have different lengths because $d>0$, so they cannot be equal. This contradiction to the pumping lemma for regular languages proves

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