Regular expression deppending on number of characters and presence of specific characters

Question

My alphabet is {0,1}. I want to match a token with an odd (or even) number of symbols, but it must contain at least one 0 and at least one 1. I tried this regular expression:

^(?=0*?1)(?=1*?0)[01](?:[01]{2})*

but it matches 11111 if the input is 111110 and it is not correct.

@nhahtdh, I dont't think I understand what you mean by "anchor". — Dani Grosu, Nov 11 '14 at 16:35
Ok, but in this case if my input is `111100`, I have no match and I shoud have `11110`. — Dani Grosu, Nov 11 '14 at 16:40

score 2 · Accepted Answer · edited May 23 '17 at 10:26

Since this sounds like automata theory, so here is an answer based on that.

You should be able to come up with the 7-state DFA below:

^{Click on the image to see enlarged version.}

The DFA on the left is for even length string and the one on the right is for odd length string. The label on the state is "[current length (odd or even)]/[0 encountered][1 encountered]".

Then you can solve the equation for the final state... or just use JFLAP to do all that for you.

Regular expression for odd-length string (can be used in your favorite regex flavor):

((11)+0|(00)+1|(10|01|(11)+10|(00)+01)[10])([10]{2})*

And for even-length string:

(10|01|(11)+(10|0[10])|(00)+(01|1[10]))([10]{2})*

Regular expression deppending on number of characters and presence of specific characters

1 Answers1