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^*$

Improve this question
$\endgroup$

2 Answers 2

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

Improve this answer
$\endgroup$
0
0
$\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^*$

Improve this answer
$\endgroup$

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.