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.

Improve this question
$\endgroup$

1 Answer 1

Reset to default
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$.

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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