1
$\begingroup$

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.

$\endgroup$
4
$\begingroup$

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

$\endgroup$
  • 2
    $\begingroup$ To make this a complete answer, note that the third regular expression describes $\Sigma^*$. $\endgroup$ – Raphael Jun 26 '15 at 7:21

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.