能被9整除的二进制数的正则表达式

Question

我想为可被 9, 18, 36, ...整除的非空二进制序列编写正则表达式，根据序列末尾的零计数，每个序列都有自己的正则表达式，并且所有正则表达式都将具有相同的基础。

这是 9 的余数表：

from #     : 0 1 2 3 4 5 6 7 8
to 2*# + 0 : 0 2 4 6 8 1 3 5 7  mod 9
to 2*# + 1 : 1 3 5 7 0 2 4 6 8  mod 9
         |   ^-^-^-^-^-^-^-^-^- vertices
       edges

通过这些余数，我为 DFA 制作了一个图表

正则表达式必须尽可能短或长一点，但要美观。

正则表达式将用于许多不同的编程语言。因此，您可以针对您喜欢的语言提出特定的表达方式。

Answer 1

我的可被 9 整除的数字的简短版本：

 (0|1((01|1(00|110)*10)(11)*0)*(0(11)*0|1(00|110)*(01|111|101(11)*0))\
(01*0((10|0(11|001)*01)(00)*1)*(1(00)*1|0(11|001)*(10|000|010(00)*1)))*1)+

删除空格和反斜杠后为 142 个字符：

(0|1((01|1(00|110)*10)(11)*0)*(0(11)*0|1(00|110)*(01|111|101(11)*0))(01*0((10|0(11|001)*01)(00)*1)*(1(00)*1|0(11|001)*(10|000|010(00)*1)))*1)+

我的可回收版本，用于可被 9 整除的数字：

 (0|1(01(11)*0|1(00|110)*(        10  (11)*0))*\
     (0 (11)*0|1(00|110)*( 01|111|101 (11)*0)) \
(01*0(10(00)*1|0(11|001)*(        01  (00)*1))*\
     (1 (00)*1|0(11|001)*( 10|000|010 (00)*1)) \
)*1)+

删除空格和反斜杠后为 154 个字符：

(0|1(01(11)*0|1(00|110)*(10(11)*0))*(0(11)*0|1(00|110)*(01|111|101(11)*0))(01*0(10(00)*1|0(11|001)*(01(00)*1))*(1(00)*1|0(11|001)*(10|000|010(00)*1)))*1)+

对于可被 (9 * 2^N) 整除的数字：

# divisible by 18
^(0+|(0*1(01(11)*0|1(00|110)*(10(11)*0))*(0(11)*0|1(00|110)*(01|111|101(11)*0))\
    (01*0(10(00)*1|0(11|001)*(01(00)*1))*(1(00)*1|0(11|001)*(10|000|010(00)*1)))*1)+0+)$

# divisible by 36
^(0+|(0*1(01(11)*0|1(00|110)*(10(11)*0))*(0(11)*0|1(00|110)*(01|111|101(11)*0))\
    (01*0(10(00)*1|0(11|001)*(01(00)*1))*(1(00)*1|0(11|001)*(10|000|010(00)*1)))*1)+0{2,})$

# divisible by 72
^(0+|(0*1(01(11)*0|1(00|110)*(10(11)*0))*(0(11)*0|1(00|110)*(01|111|101(11)*0))\
    (01*0(10(00)*1|0(11|001)*(01(00)*1))*(1(00)*1|0(11|001)*(10|000|010(00)*1)))*1)+0{3,})$