# 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