1
$\begingroup$

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.

  • 0
    As you can see from the answers, there are (at least) two ways to go about this: (a) the formal, algorithmic method using known algorithms (convert RE to DFA; invert DFA; determine if DFA$_1$ and DFA$_2$ accept the same language); (b) reason informally to get a set & symbol-theoretic definition for the two languages and reason, again informally, to show those two definitions are complementary. Or you could reason (b) more formally, but it's not worth it for these relatively simple REs. IAC, you might set the context for which method is expected of you at this place in the course and text. – 2012-03-13

3 Answers 3

1

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.

  • 0
    @Raphael: he can't upvote yet. – 2012-03-13
1

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

0

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?

  • 0
    @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). – 2012-03-13