CODEWITHSUNDEEP
regexcomputer-sciencecomputation-theory
user595334
user595334

Reputation:

Regular Expression that matches based on differences in 1's in 0's in a binary string

So, it's finals time and I came across this problem in an old exam:

Give a regular expression that denotes diff(x) where:

- diff(x) is the number of 1's in x minus the number of 0's in x
- 1 <= diff(x) <= 3

e.g. 

 diff(10110100111) = 7-4 = 3
 diff(11100011) = 5-3 = 2
 diff(10011) = 3-2 = 1

Upvotes: 3

Views: 158

Answers (2)

collapsar
collapsar

Reputation: 17238

it should not be possible to build a regex as desired. if it was you'd have a finite state automaton necessarily implementing an unbounded counter in order to distinguish between inputs 0^n1^n111 and 0^n1^n1111. obviously this cannot be achieved, at least in terms of theory (it can be achieved, however, if the difference between the number of 1s and 0s in any prefix of x is bounded by a constant).

that might be irrelevant in practice as virtually every common regex engine is more powerful than a regex recognizer but it might be relevant in the context of an exam question.

Upvotes: 2

Lucero
Lucero

Reputation: 60190

Not sure about the regex engine you're addressing, you need one with some recursion support such as .NET (balancing groups) or PCRE (recursion). The following is valid and works in .NET:

^((?<-Z>1)|(?<-O>0)|(?<O>1)|(?<Z>0))*$(?<-O>)(?<-O>)?(?<-O>)?(?(O)(?!))(?(Z)(?!))

Upvotes: 1

Related Questions