# Regular expression for all strings with at least two 0s over alphabet {0,1}

My answer : (0+1)* 0 (0+1)* 0 (0+1)*

Why is this incorrect? Can somebody explain to me what the correct answer is and why?

• The regular expression is correct. – rgrig May 10 '12 at 17:35
• Looks good to me. Who says not? – David Lewis May 10 '12 at 17:40
• A simpler expression would be $1^*01^*0(0|1)^*$. – Artem Kaznatcheev May 10 '12 at 22:12
• @kaveh $(0+1)$ is quite standard, I see no confusion here. It is used interchangeably with $(0|1)$ and $(0\cup1)$. – Ran G. May 11 '12 at 1:42
• @Kaveh I have no doubt in your means. Yet, the OP might not understand the ambiguity (especially if the OP is new to this). IMHO, the answer of svick is the one that should be clarified as it uses the plus sign in a non-orthodox way. – Ran G. May 11 '12 at 5:43

It's incorrect for example because it does not match the string $100$.

The two zeroes would have to match the two zeroes in your regexp that are ouside the parentheses. Because of that, $(0\!+\!1)^*$ would have to match $1$, but it doesn't. That's because $(0\!+\!1)^*$ implies there has to be at least one zero for every $1$.

I think the regular expression that you meant is:

$$(0|1)^* 0 (0|1)^* 0 (0|1)^*.$$

• I think the OP thought that $+$ meant the same as $|$, in fact, I thought that too when I read the question, but checking wikipedia does tell me that I am wrong, since $a+$ just means $aa^*$. – Artem Kaznatcheev May 10 '12 at 22:15
• Yeah, that's most likely. And other people here probably thought the same. – svick May 10 '12 at 22:16
• I think it would be helpful if you stressed that in your answer more (i.e. that $a+b$ does not mean $a|b$ but means $aa^*b$). – Artem Kaznatcheev May 10 '12 at 22:17
• What? $a+b$ does mean alternation in most theoretical treatments of regular expressions. E.g., books.google.co.uk/… – rgrig May 10 '12 at 22:54
• @Artem: I am pretty sure $a+b$ is not standard notation for $a a^*b$? Probably $a^+b$ might be. Where on Wikipedia did you see $a+$ meaning $aa^*$? – Tara B May 11 '12 at 8:36