Regular Expression for Binary Numbers Divisible by 5

regex binary division
The Beast picture The Beast · Dec 27, 2015 · Viewed 14.7k times · Source

I want to write a regular expression for Binary Numbers Divisible by 5.
I have already done the regular expressions for Binary Numbers Divisible by 2 and for 3 but I couldn't find one for 5.

Any suggestions?

Answer

ndnenkov picture ndnenkov · Dec 27, 2015 
(0|1(10)*(0|11)(01*01|01*00(10)*(0|11))*1)*

Add ^$ to test it with regexp. See it working here.

You can build a DFA and convert it to regular expression. The DFA was already built in another answer. You can read it, it is very well explained.
The general idea is to remove nodes, adding edges. before

Becomes:

after

Using this transformation and the DFA from the answer I linked, here are the steps to get the regular expression:
(EDIT: Note that the labels "Q3" and "Q4" have been mistakenly swapped in the diagram. These states represent the remainder after modulus 5.) step1 step2 step3 step4 step5

Related questions

Regular expression to match a line that doesn't contain a word

I know it's possible to match a word and then reverse the matches using other tools (e.g. grep -v). However, is it possible to match lines that do not contain a specific word, e.g. hede, using a regular …

Read More
How to validate an email address in JavaScript

Is there a regular expression to validate an email address in JavaScript?

Read More
RegEx match open tags except XHTML self-contained tags

I need to match all of these opening tags: <p> <a href="foo"> But not these: <br /> <hr class="foo" /> I came up with this and wanted to make sure I've got …

Read More