How to write a regular expression for every string w over {0,1} where w is a binary string with value of at least 40.

Question

So far I have realized that minimum value is 101000 in binary, but we also have to accept strings like 110000 and 1000000.

I came up with

r = (0+1)^* 1 (01+10+11) (0+1)^3

but then realized the string could also be 10000000. I'm not sure how to take into consideration that any 1's after the six digit from the left will also take the value over $40$.

Any help would be greatly appreciated.

Answer 1

I will leave writing the regex to you, but I would write a regex that checks two things:

• If the number is $101$, $110$ or $111$, followed by any three characters, then match.
• If the number is $1$, followed by any $6$ characters, followed by any number (including zero) of other characters then match.

Otherwise, do not match.

The first condition matches all numbers from 101000 (that is, $40$) to 111111 (that is, $63$).

The second conditions matches all numbers, greater than 1000000 (that is, $64$.

---

Note that you might want to also consider if you want to handle leading zeroes, but that shouldn't make it much harder.

Answer 2

Even if you can't think of anything clever, you could do something brute-force. Suppose $A$ was a regex that matched all the numbers that are at least 64. That might not be too hard to come up with. Then you could do $$\mathtt{101000} + \mathtt{101001} + \cdots +\mathtt{111111} + A.$$