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