How do up you show that two that the regular expressions, such as $(01+1)^*$ and $(0+1)^*\left(0 + 00(0+1)^*\right)$ represent complementary regular languages over $\{0,1\}$? I'm trying to do some problems from my textbook (An Intro to Formal Lang and Automata by Linz) but I'm stuck on this problem.
Any help would be great, thanks.
On
A more informal proof would be to reformulate what the regular expressions do in natural language:
00s, and doesn't end with 0. 0 and also everything that contains 00.It should then be clear that every possible string is in exactly one of the two languages -- you can determine which one simply by looking at the string: Does it end with 0? Is there a 00 somewhere in there?
On
$(01+1)^*$ represents the language consisting precisely of those words in which every $0$ (if there is one) is immediately followed by a $1$. This excludes all words containing $00$ and all words that end in $0$, and nothing else. An easy way to see this is to realize that $(01+1)^*$ describes the language the same language that you get if you start with $\{1,2\}^*$ (corresponding to the regular expression $(2+1)^*$) and replace each $2$ in every word by $01$. The resulting word clearly must end in $1$ and clearly cannot contain $00$, but it’s not hard to show that it contains everything else.
I assume that your other regular expression is supposed to be $(0+1)^*[0+00(0+1)^*]$; the two $(0+1)^*$ expressions allow the generation of arbitrary strings, so the language is everything of the form $u0$ with $u\in\{0,1\}^*$ together with everything of the form $u00v$ with $u,v\in\{0,1\}^*$ $-$ in other words, everything that either ends in $0$ or contains $00$, precisely the complement of the first language.
That is easy because $\mathrm{REG}$ is closed against complementation and inclusion can be decided.
Converting all final states to non-final states and vice versa will cause the resulting automaton to accept the complement of the original one.
Are you clear on those steps? Otherwise I can elaborate.