CODEWITHSUNDEEP
regex
Kevinniceguy
Kevinniceguy

Reputation: 143

Regular expression for strings with an even number of zeroes and ones

What is a regular expression for strings of 0 and 1 with an even number of zeros and an even number of ones?

I have something like (1*01*01*)*(0*10*10*)*.

Does it look good?

Upvotes: 8

Views: 12732

Answers (4)

jing
jing

Reputation: 9

@tmp = $str =~ /0/g;

print scalar @tmp % 2 == 0 ? 'even' : 'odd';

Upvotes: -1

Jim Lewis
Jim Lewis

Reputation: 45045

1100 is in the language, but doesn't match your expression. 10101 is not in the language, but your expression matches it.

I'd suggest starting by drawing a DFA. There's a pretty obvious 4-state machine that recognizes this language. (Is it possible to do better?) The empty string is in the language, so the start state is an accepting state. Are there other accepting states? For a non-accepting state S, is there a prefix that takes you from start->S? Is there a way to loop from S back to S without hitting an accepting state? Is there suffix that takes you from S back to an accepting state?

Upvotes: 6

tloflin
tloflin

Reputation: 4050

Well, this is probably homework, but what the heck:

^(00|11|(01|10)(00|11)*(01|10))*$

Edit: simplified!

Upvotes: 15

Greg Hewgill
Greg Hewgill

Reputation: 993015

A counterexample for your given regular expression is 01010101.

You may find that writing a regular expression for this particular problem is not going to be possible (unless you use some non-regular extensions to the usual regular expression language).

As mentioned by Jim Lewis below, this should indeed be a solvable problem.

Upvotes: 1

Related Questions