# Showing that two regular expressions represent complementary regular languages over {0,1}

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.

-
Are you sure your expressions are complementary? (Or I don't understand your notations with $[$ and $]$, but then please explain.) As to how to prove such a thing, the brute-force method is to create minimal automatas and show they are isomorphic but for the sets of final states, which should be the complements of each other. – dtldarek Mar 13 '12 at 19:19
Note that this question would have been perfect for cs.SE which will enter public beta soon! – Raphael Mar 13 '12 at 19:24
@dtldarek I got those expressions directly out of the book, so they probably are complementary. Please ignore the [], that was a typo on my part, they're not meant to be there, sorry. – Momagic Mar 13 '12 at 19:33
@Momagic I guess it's better now after the edit by Henning (the Markdown was eating up the stars before). – dtldarek Mar 13 '12 at 19:36
@Momagic: It was right before you removed the square brackets (which I assumed to be just a typographical variant of parentheses here). Now, on the other hand, 1001 is in neither language. – Henning Makholm Mar 13 '12 at 19:39

That is easy because $\mathrm{REG}$ is closed against complementation and inclusion can be decided.

1. Transform both to DFA.
2. Invert one of them.
Converting all final states to non-final states and vice versa will cause the resulting automaton to accept the complement of the original one.
3. Decide wether both DFA accept the same language.

Are you clear on those steps? Otherwise I can elaborate.

-
Can you elaborate please? I'm not sure what you mean by invert. – Momagic Mar 13 '12 at 19:28
Thank you, that makes sense. I'll try it out. Thanks so much for your help. – Momagic Mar 13 '12 at 19:37
@Momagic Please remember to upvote answers you like and accept the one you liked best. – Raphael Mar 13 '12 at 19:41
@Raphael: he can't upvote yet. – Henning Makholm Mar 13 '12 at 19:49

$(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.

-
Thank you so much for your help! – Momagic Mar 13 '12 at 19:48

A more informal proof would be to reformulate what the regular expressions do in natural language:

• The first one matches every string that doesn't contain 00s, and doesn't end with 0.
• The second one matches everything that ends with 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?

-
Or even one can set $A = (0+1)^*1$, $B = (0+1)^*00(0+1)^*$ and explain why first equals $A \cap \neg B$ and second equals $\neg A \cup B$. – dtldarek Mar 13 '12 at 19:40
@dtldarek: I'm not convinced that would be much clearer. (Also, I don't think $\neg$ is kosher to use with sets rather than logical formulas). – Henning Makholm Mar 13 '12 at 19:42
Thank you so much for your help! – Momagic Mar 13 '12 at 19:47