# Why a language specified by a regular expression is not a complement of a given language?

I am taking a compiler MOOC online on my own time. The class is self paced. There is a question with an answer but I can't understand why the answer is correct.

Here is the question.

For any language $L$, the complement of the language (usually written $L′$) is defined as the language that consists of all the strings that are NOT in $L$. That is,

$L′=Σ^*−L$

It turns out that the complement of any regular language is also a regular language. Which of the following regular expressions define a language that is the complement of the language defined by the regular expression: $1(01)^*$?

1. $(10)^*+\big((10)^*0(0+1)^*\big)+\big(1(01)^*1(0+1)^*\big)$
2. $\epsilon + (0(0 + 1)^*) + ((0 + 1)^*0) + \big((0 + 1)^*(00 + 11)(0 + 1)^*\big)$
3. $(0 + \epsilon)\big((1 + \epsilon)(0 + \epsilon)\big)^*$
4. $(10)^*$

Correct answers are 1 and 2. I can't understand why 3 and 4 are not correct as well since the strings generated by these languages are also not in $L$.

Any explanation is greatly appreciated.

The complement of a language $L$ should contain all strings not in $L$. Your language $L$ doesn't contain the word $0$, which the language $(10)^*$ also doesn't contain – so $(10)^*$ can't be the complement of $L$.
• To make this a complete answer, note that the third regular expression describes $\Sigma^*$. – Raphael Jun 26 '15 at 7:21