CODEWITHSUNDEEP
regex
user801154
user801154

Reputation:

Regular expression for equal number of 0 and 1

How to find regular expression with equal number of 1 and 0. I am also interested in how you think such solution ?

example: should match : 1100, 00100111 , 01 . shouldn't match: 110 , 0, 11001.

I need regular expression which gives set of all such string . If length of string in set given by regular expression in 2n then number of 0s should be equal to number 1s = n.

Upvotes: 5

Views: 20555

Answers (4)

LucieCBurgess
LucieCBurgess

Reputation: 799

It is not possible to generate a regular expression for the language L = (0,1) (same number of 1s and 0s).

This is not a regular language, so cannot be described with a regular expression. It's not regular because an automaton which accepts it would need differing amounts of memory depending on the length of the input. A regular language is one which uses constant memory, regardless of the length of the input.

The language you describe can be generated by a Context Free Grammar, but not a regular expression.

The following CFG generates strings where the numbers of 0s and the number of 1s are equal. If S is any word in the language:

S -> SS
S -> 0S1
S -> 1S0
S -> ε (the empty word)

For this language you need a stack, and a pushdown automaton could be designed to accept it, or a Turing machine.

Upvotes: 15

Jens
Jens

Reputation: 25563

Here is a regex pattern for the .NET engine that does satisfy your needs. See it in action at ideone.com.

^((?(D)(?!))(?<C>1)|(?(D)(?!))(?<-C>0)|(?(C)(?!))(?<D>0)|(?(C)(?!))(?<-D>1))*(?(C)(?!))(?(D)(?!))$

It works by using two stacks, using one (C) if there are curretly more 1s than 0s and the other one (D) if there are more zeroes than ones.

Not pretty, definitely not usable, but it works. (Ha!)

Upvotes: 4

twalberg
twalberg

Reputation: 62379

While this is not possible with a regular grammar as stated in another answer, it should be relatively easy to scan the string, increment a counter for each 1 and decrement it for each 0. If the final count is 0, then the number of 0s and 1s is equal (modulo 2^wordsize - watching out for overflow would make it a little trickier, but depending on whether there are other assumptions that can be made regarding the input, that may not be necessary).

Upvotes: 1

Nahuel Fouilleul
Nahuel Fouilleul

Reputation: 19315

Not possible with regular grammar (finite state automaton) : http://en.wikipedia.org/wiki/Regular_language

Upvotes: 5

Related Questions