Home ยป Regular expression to match all binary strings with even number of ones and zeros [closed]

Regular expression to match all binary strings with even number of ones and zeros [closed]

Solutons:


You expression is almost correct, the use of (2|3) will cause issues, as these will match their content, but not their syntax. So certain examples should fail:

011101

Because the 11 can’t be substituted by 3, as the capture is empty at that point in time. So you’ll have to duplicate the syntax:

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

Then there is some additional optimization you can do. Instead of repeating each internal group 0..* times and the out group 1..* times, you can remove the inner repetition and change the outer one to 0..*:

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

Further simplification doesn’t seem possible without resorting to tricks such as zero-width assertions, basically ensuring that you end up with an even number of 1’s and and even number of 0’s and ensuring that both are true:

^(?=0*((10*){2})*$)1*((01*){2})*$

Cheating a bit further, we already know by the capturing expression that we have an even number of 0’s, so we can replace the look-ahead to just ensure we’re on an even number of characters, there are no other characters to worry about:

^(?=(.{2})*$)1*((01*){2})*$

It’s slightly shorter and notice that the first part of the expression is zero-width, the second part is not to ensure that we actually end up with a capture.

The final trick, completely moving away from a DFA, is to use balancing groups, since we’re balancing 1’s and 0’s we know we’re even when every odd 1 and 0 has been balanced by its even counterpart. It’s not really simpler, but it does work and only needs one pass, like your example:

^((((?<z>0)|(?<o>1))|((?<-z>0)|(?<-o>1))))*(?(z)(?!))(?(o)(?!))$

There is an algorithm to convert a DFA into a regular expression.

A good explanation is given by in the StackExchange answer: How to convert finite automata to regular expressions?

Here is a demonstration of how it applies to this problem:

We start with this DFA:

enter image description here

and we first remove the OO node yielding:

enter image description here

Next, remove, say, the OE node:

enter image description here

Finally, remove the EO node. The paths from EE to itself are:

r1: 00
r2: 0(11)*0
r3: (0(11)*10 | 1)  (00 | 01(11)*10 )* (1 | 01(11)*0 )
      _ to EO _/    _ around EO _/   _ back to EE _/

The final regex is: (r1 | r2 | r3)*.

This problem is easier to solve with a lookahead combination than with a “match all possibilities” combination. Consider two zero-width lookaheads before the first character. One ensures that each 1 has a following matching 1, and the other ensures that each 0 has a matching 0. if you can guarantee that there are only 1 and 0 characters in the code then you’re set.

So, your issue here is that you are trying to count mixed up bit values, but separating them makes the logic much easier:

^(?=(1*01*0)*1*$)(?=(0*10*1)*0*$).*$

Note, there are two lookaheads, and combining them like this essentially makes them two “and” conditions.

The first is:

(?=(1*01*0)*1*$)

That says:

  1. find a 0-bit pair that has some number (perhaps 0) 1 bits before them
  2. allow that pattern to repeat as many times as needed (perhaps 0)
  3. then allow there to be other 1 bits after them to the end of string.

This ensures that there are an even number of 0 values, and all other values are 1’s.

The second regular expression is the opposite, it ensures there’s an even number of 1 bits, and the other bits are 0.

Combine them together and you can count them easily….

See the pattern working in Java here.

Note that my preference solution would simply be to ensure there are an even number of characters in total (a length % 2 == 0) and then to just ensure an even number of the 0-bits:

^(1*01*0)*1*$

use that as:

return (text.length % 2 == 0) && text.matches("^(1*01*0)*1*$")

That eliminates all the lookaheads and other magic.

Related Solutions

Default value for UUID column in Postgres

tl;dr Call DEFAULT when defining a column to invoke one of the OSSP uuid functions. The Postgres server will automatically invoke the function every time a row is inserted. CREATE TABLE tbl ( pkey UUID NOT NULL DEFAULT uuid_generate_v1() , CONSTRAINT pkey_tbl...

comparing five integers with if , else if statement

try this : int main () { int n1, n2, n3, n4, n5, biggest,smallest; cout << "Enter the five numbers: "; cin >> n1 >> n2 >> n3 >> n4 >> n5 ; smallest=biggest=n1; if(n2>biggest){ biggest=n2; } if(n2<smallest){ smallest=n2;...

How to play YouTube audio in background/minimised?

Here's a solution using entirely free and open source software. The basic idea is that although YouTube can't play clips in the background, VLC for Android can play clips in the background, so all we need to do is pipe the clip to VLC where we can listen to it...

Why not use “which”? What to use then?

Here is all you never thought you would ever not want to know about it: Summary To get the pathname of an executable in a Bourne-like shell script (there are a few caveats; see below): ls=$(command -v ls) To find out if a given command exists: if command -v...

Split string into Array of Arrays [closed]

If I got correct what you want to receive as a result, then this code would make what you want: extension Array { func chunked(into size: Int) -> [[Element]] { return stride(from: 0, to: self.count, by: size).map { Array(self[$0 ..< Swift.min($0 + size,...

Retrieving n rows per group

Let's start with the basic scenario. If I want to get some number of rows out of a table, I have two main options: ranking functions; or TOP. First, let's consider the whole set from Production.TransactionHistory for a particular ProductID: SELECT...

Don’t understand how my mum’s Gmail account was hacked

IMPORTANT: this is based on data I got from your link, but the server might implement some protection. For example, once it has sent its "silver bullet" against a victim, it might answer with a faked "silver bullet" to the same request, so that anyone...

What is /storage/emulated/0/?

/storage/emulated/0/Download is the actual path to the files. /sdcard/Download is a symlink to the actual path of /storage/emulated/0/Download However, the actual files are located in the filesystem in /data/media, which is then mounted to /storage/emulated/0...

How can I pass a command line argument into a shell script?

The shell command and any arguments to that command appear as numbered shell variables: $0 has the string value of the command itself, something like script, ./script, /home/user/bin/script or whatever. Any arguments appear as "$1", "$2", "$3" and so on. The...

What is pointer to string in C?

argv is an array of pointers pointing to zero terminated c-strings. I painted the following pretty picture to help you visualize something about the pointers. And here is a code example that shows you how an operating system would pass arguments to your...

How do mobile carriers know video resolution over HTTPS connections?

This is an active area of research. I happen to have done some work in this area, so I'll share what I can about the basic idea (this work was with industry partners and I can't share the secret details ๐Ÿ™‚ ). The tl;dr is that it's often possible to identify an...

How do I change the name of my Android device?

To change the hostname (device name) you have to use the terminal (as root): For Eclair (2.1): echo MYNAME > /proc/sys/kernel/hostname For Froyo (2.2): (works also on most 2.3) setprop net.hostname MYNAME Then restart your wi-fi. To see the change, type...

How does reverse SSH tunneling work?

I love explaining this kind of thing through visualization. ๐Ÿ™‚ Think of your SSH connections as tubes. Big tubes. Normally, you'll reach through these tubes to run a shell on a remote computer. The shell runs in a virtual terminal (tty). But you know this part...

Difference between database vs user vs schema

In Oracle, users and schemas are essentially the same thing. You can consider that a user is the account you use to connect to a database, and a schema is the set of objects (tables, views, etc.) that belong to that account. See this post on Stack Overflow:...

What’s the output of this code written in java?

//if you're using Eclipse, press ctrl-shift-f to "beautify" your code and make it easier to read int arr[] = new int[3]; //create a new array containing 3 elements for (int i = 0; i < 3; i++) { arr[i] = i;//assign each successive value of i to an entry in...

How safe are password managers like LastPass?

We should distinguish between offline password managers (like Password Safe) and online password managers (like LastPass). Offline password managers carry relatively little risk. It is true that the saved passwords are a single point of failure. But then, your...