[Math] Showing that two regular expressions represent complementary regular languages over {0,1}

automatacomputer scienceformal-languages

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.

Best Answer

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.

Related Question