Regular expression: Complement of 10 in alphabet {0,1}

Question

I have the alphabet {0,1}, and I want to find the complement of the language described by the regular expression (0+10)*. As far as I understand, it must be a string containing anything but the part "10", namely it can be an empty string, or a string containing "00", "01", or "11" and every combination of these. The tutorial I am following gives these possible solutions that I can't fit the answer in:

1)      (0+1)*11(0+10)* + (0+1)*1
2)      (0+1)*11(0+10)* + (0+10)*1
3)      (0+1)*(1+11)(0+1)*
4)      (0+10)*11(0+10)*

I have been through the proces of e-NFA, DFA, and back to a regular expression which can be seen here: e-NFA, DFA and complemented DFA

With 1, 2, 3, and 4 given by:

1 = {B, C, D, E}
2 = {B, C, D, E, F, H}
3 = {I}
4 = {B, C, D, E, G, H}

Which gives me the following complemented regular expression that doesn't seem to be any near 1 through four above:

(1+00*1)*(0(1+00*1))* = 0(1+00*1)

I hope someone can clarify this. Thanks in advance, J.

What flavor regex are you using? Can you offer more about what you are trying to match and what you've tried? What does "the complement of the language described" mean? — jmargolisvt, Sep 19 '15 at 01:26
Note that the complement can't include the empty string, because the language you're complementing includes it. — Mark Reed, Sep 19 '15 at 01:33
If `10` is not possible, then as soon as you get a `1`, then `0` is forbidden. Unless I misunderstand your description of what the input can really be. i.e. the solution would be `0*1*` plus a little something to avoid the empty string (i.e. `0+1*|0*1+`) — Alexis Wilke, Sep 19 '15 at 01:44
As I read it, the input can be any string of 0's and 1's including the empty string, and every 1 must be followed by a zero. This is what I need the complement of. — J. P., Sep 19 '15 at 02:40

score 0 · Answer 1 · edited May 23 '17 at 11:58

So in general you have to go through a deterministic finite automaton to complement a regular expression. (See this question.) But you may be able to do it by inspection here.

The regex ^(0+10)*$ matches the empty string plus all other binary strings that start with 0, end with 10, and have at least two 0s between any pair of 1s. (I'm assuming that the regular expression is meant to be anchored; if it matches all strings that contain a match, this becomes a harder problem.)

The complement therefore includes only nonempty binary strings that either start with 1, end with 1 or 00, or include 11 or 101 anywhere in them. Here's one way to encode that as a regular expression:

(^1|(1|00)$|10?1)

But there are no doubt simpler ways.

I tried to follow the general way, but my answer doesn't seem to be correct, yet. — J. P., Sep 19 '15 at 02:31

Regular expression: Complement of 10 in alphabet {0,1}

1 Answers1