Write a regular expression for all the strings in which every pair of adjacent zeros appears before any pair of adjacent ones. The answer given in the book is: $$(0+10)^*(00)(1+01)^*(11)(0+10)^*(1+01)^*$$ Is that correct? I fail to see how could you get a string like 10011, but it fits description. I mean even a string like 1 fits a description. So, if this answer is incorrect, then what is a correct answer? My simple guess is: $$(\epsilon+1)(0+10)^*(1+01)^*(\epsilon+0)$$

P.S. Does $(0^*1^*)^*$ generate every possible binary number? If not, what does it generate?

  • $\begingroup$ Not to mention that the book answer won't generate 11. $\endgroup$ – Rick Decker Dec 8 '14 at 19:56
  • $\begingroup$ Your answer is incorrect, since it generates $1100$. $\endgroup$ – Yuval Filmus Dec 8 '14 at 19:57
  • $\begingroup$ My guess is $(0+10)^*(1+10)^*$. $\endgroup$ – Yuval Filmus Dec 8 '14 at 20:03
  • 2
    $\begingroup$ For languages such as this, it's sometimes easier to construct an NFA and convert it. That siad, I'm confused by "every" and "any" (note that title != text). For instance, is $00$ forbidden after $11$? $\endgroup$ – Raphael Dec 8 '14 at 20:11

You are correct: the regexp you quote does not match the string $10011$ and that string has the property that every pair of adjacent $0$s occurs before any pair of adjacent $1$s. But it does match the string $001100$, which fails to have the property!

Your proposed solution matches $11001$ so is also incorrect (the first bracket matches $1$, the second matches $10$, the third matches $01$ and the fourth matches $\epsilon$.

A regexp that does match the required language is $$0^*(100^*)^*(11^*0)^*1^*\,.$$ It works as follows.

  • $0^*(100^*)^*$ matches the empty string and any non-empty string that doesn't contain $11$ and that ends with $0$. The string can't contain $11$ because there must be at least one $0$ between every two $1$s.

  • $(11^*0)^*1^*$ matches every string that begins with $1$ and does not contain $00$, since there must be at least one $1$ between any two $0$s.

  • Now put the two halves together. If a string has the property that all occurrences of $00$ are before the first $11$, then the section of the string before the first $11$ must either be empty or end in $0$, so it matches the first part of the regexp. The rest of the string contains no occurrences of $00$ so it matches the second part of the regexp.

Note that there are shorter regexps that do the same thing: Yuval Filmus gives $(0+10)^*(1+10)^*$ in a comment to the question. That's a tidier version of the same idea.

And, yes, $(0^*1^*)^* \equiv (0+1)^*$ matches every possible binary string.

  • $\begingroup$ Can you please give me the name of your texbook you got that answer from? $\endgroup$ – Shahul Es Sep 27 '18 at 5:06
  • 1
    $\begingroup$ I didn't get it from any textbook and I'm kind of insulted that you think that I'd (a) not be able to solve this for myself and (b) not credit the source of the answer if I had taken it from somewhere else. $\endgroup$ – David Richerby Sep 27 '18 at 11:00

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.