Problem $1\mathrm{.}1$: Let Lsube$\{0,1{\}}^{**}$ be the language defined recursively as follows:

The empty string $$ is in $L.$

For any string $x$ in $L,$ the strings $1x01$ and $11x0$ are also in $L.$

For any strings $x,y$ such that $xy$ is in $L,$ the string $x011y$ is also in $L.($In other words,

inserting $011$ anywhere to a string in $L$ yields another string in $L.)$

The only strings in $L$ are those that can be obtained by the above rules.

Define $L_{\text{d}\text{o}\text{u}\text{b}\text{l}\text{e}}=\{xin\{0,1{\}}^{**}$:#${?}_1(x)=2$#${?}_0(x)\},$ where #${?}_a(x)$ denotes the number of

occurrences of the symbol $a$ in the string $x.$

$($a$)$ Prove that $Lsube{L}_{\text{d}\text{o}\text{u}\text{b}\text{l}\text{e}},$ by using induction. $($You should use strong induction.$)$

$($b$)$ Conversely, prove that $L_{\text{d}\text{o}\text{u}\text{b}\text{l}\text{e}}$subeL, by using induction.

$[$Hint: What does a string that does not contain $011$ as a substring look like? It

may be helpful to decompose the string into blocks of $0\text{'}$s and $1\text{'}$s $($i$.$e$.,$ write it as

$0^{i_1}{1}^{j_1}{0}^{i_2}{1}^{j_2}$cdots$0^{i_k}{1}^{j_k}$ with $i_1,j_1,$dots,$i_k,j_{k}1,$ if it starts with a $0$ and ends with a $1$ ;

and similarly for the other cases$).]$