Finding a regular expression for all non-empty binary strings that contain both 0s and 1s but no consecutive 1s

Question

This is for formal-language-style regular expression and not about Unix-style regular expression.

I was trying to find the regular expression that doesn't accept empty string, doesn't accept strings composed of only 0's, and doesn't accept strings composed of only 1's. The regular expression should only accept strings composed of 0's and 1's but without consecutive 1's.

Here's what I've seen so far: $(0+10)^*(ε+1)$

The problem is that it can accept empty string or just 1-character string 1. I would like to skip empty string and 1 since they are not strings of 0's and 1's.

I just couldn't find a good pattern. It seems that I have to create 2 regular expressions so that the first will be $(01+10)(0+1)^*$. If I am right, that will not accept empty string, will not accept just 0's, and will not accept just 1's. Then I would pass the result to the 2nd pattern $(0+10)^*(ε+1)$ to further validate that it has no consecutive 1's.

Could anyone explain what is the best solution to have the correct regular expression for strings of 0's and 1's?

Answer 1

I would suggest you to draw a small finite state automaton. Things to keep track in the states are "seen 0", "seen 1" and "last letter 1" (to avoid consecutive 1's).

There is an "official" algorithm to go from automaton to expression, but with small examples you usually can read the expression directly.

Answer 2

Starting from what you have, let's try to improve it.

So you have $(0+10)^*(ε+1)$. That's a very good start, as it covers all binary strings with no consecutive 1s. I think of this as saying that a binary string with no consecutive 1s is like a string made up of 0 and 10 sequences, with an optional 1 added at the end.

Now, as you want only non-empty strings, and furthermore want strings that contain both a 0 and a 1, let's extend that so that we have at least one 10 sequence: $0^*10(0+10)^*(ε+1)$

Now, the only case not covered is the case where there is no 10 in the string at all - that is, where we have one or more 0s and then a final 1, so we add that: $0^*10(0+10)^*(ε+1) + 00^*1$

Answer 3

You can at least use two regex' in parallel instead of your chained solution. In Unix syntax it could look like this (should be easily translatable to your style):

(10+)+1?|(0+1)+0?

The first regex forces a group of zeros after every 1 while the latter forces a group of zeros before a 1.