0
$\begingroup$

Can anyone help me figure out the error in my approach to this problem from Sipser 1.18 (1.6f)? Write a regular expression for the language L = {w | w does not contain 110}

enter image description here enter image description here enter image description here enter image description here

So, the answer I get is: $(0 \cup 10)^* (1 \cup 111^* \cup \epsilon)$

And the answer given is: $(0 \cup (10)^*)^*1^*$

$\endgroup$

3 Answers 3

1
$\begingroup$

Note that $\mathcal{L}(1\cup 111^*\cup \varepsilon) = \mathcal{L}(1^*)$.

And in the general case, $\mathcal{L}((e\cup f)^*) = \mathcal{L}((e\cup f^*)^*)$.

So your regular expression is correct.

$\endgroup$
0
1
$\begingroup$

To elaborate on Nathaniel's answer:

$1 \cup 111* \cup\space \epsilon \\ = 1(\epsilon \cup 11^*)\cup \epsilon \\ = 1(\epsilon + 1^+) \cup \epsilon \\ = 1(1^*) \cup \epsilon\\ = 1^+ \cup \epsilon \\ = 1^*$

$\endgroup$
0
$\begingroup$

Your strings can start with any number of 0's or 10's. These don't contain any 110. So we start with $(0 | 10)^*$.

The remainder of the input mustn't contain any zeroes: If the remainder starts with no 1 or one 1, then that cannot be followed by a zero, because 0 or 10 would be part of $(0 | 10)^*$. If there are $n \ge 2$ 1's, that cannot be followed by a 0 because then we would have $1^{n-2} 110$ which is by definition not part of the language. So the rest of the input is $1^*$, and the regular expression is $(0 | 10)^* 1^*$.

OP's answer is also correct, but this grammar is simpler, and any string can be parsed in one way only.

$\endgroup$

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.