Set of Binary Strings Corresponding To a Regular Expression

Question

$(1 + 01)^*(0 + 01)^*$

I'm thinking

{set of all binary strings} $-$ {set of binary strings that begin with 00 and contain 11}

Would this be correct?

Answer 1

$(1+01)^*$ generates all strings of zeroes and ones with the property that every $0$ is immediately followed by a $1$; these are the strings that do not contain $00$ and do not end in $0$. Similarly, $(0+01)^*$ generates all strings of zeroes and ones in which every $1$ is immediately preceded by a $0$; these are the strings that do not contain $11$ and do not begin with $1$.

$(1+01)^*(0+01)^*$ generates (among others) all strings that do not contain $00$: if such a string ends in $1$, it’s matched by $(1+01)^*$, and if it ends in $0$, it’s matched by $(1+01)^*0$. Similarly, it generates all strings that do not contain $11$: these strings match either $(0+01)^*$ or $1(0+01)^*$.

Suppose that a word $w$ contains both $00$ and $11$ and matches $(1+01)^*(0+01)^*$; clearly every instance of $00$ in $w$ must follow every instance of $11$. Conversely, suppose that $w$ contains both $00$ and $11$ as substrings but has all instance of $11$ before any instance of $00$. Thus, we can decompose $w$ as $w=x100y$ in such a way that $x1$ is generated by $(1+01)^*$ and $00y$ by $(0+01)^*$. Clearly all instance of $11$ are in the substring $x1$, and all instance of $00$ are in the substring $00y$. Thus, the words containing both $00$ and $11$ that match $(1+01)^*(0+01)^*$ are precisely those in which all instances of $11$ precede all instance of $00$.

Putting the pieces together, we see that $(1+01)^*(0+01)^*$ generates all bit strings that do not contain a substring $00$ to the left of a substring $11$.