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}
So, the answer I get is: $(0 \cup 10)^* (1 \cup 111^* \cup \epsilon)$
And the answer given is: $(0 \cup (10)^*)^*1^*$
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.
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^*$
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.
