Регулярное выражение для определения некоторой двоичной последовательности

Question

Как бы вы написали регулярное выражение для определения всех строк 0 и 1, которые в виде двоичного числа представляют целое число, кратное 3.

Некоторые действительные двоичные числа будут:

11
110
1001
1100
1111

Answer 1

Используя DFA здесь , мы можем сделать регулярное выражение следующим образом, где A, B, C представляют состояния DFA.

A = 1B + 0A
B = 1A + 0C
C = 1C + 0B

C = 1*0B // Eliminate recursion

B = 1A + 0(1*0B)
B = 01*0B + 1A
B = (01*0)*1A // Eliminate recursion

A = 1(01*0)*1A + 0A
A = (1(01*0)*1 + 0)A
A = (1(01*0)*1 + 0)* // Eliminate recursion

В результате регулярное выражение PCRE выглядит так:

/^(1(01*0)*1|0)+$/

Perl-тест / пример:

use strict;

for(qw(
11
110
1001
1100
1111
0
1
10
111
)){
    print "$_ (", eval "0b$_", ") ";
    print /^(1(01*0)*1|0)+$/? "matched": "didnt match";
    print "\n";
}

Выходы:

11 (3) matched
110 (6) matched
1001 (9) matched
1100 (12) matched
1111 (15) matched
0 (0) matched
1 (1) didnt match
10 (2) didnt match
111 (7) didnt match

Answer 2

Когда вы делите число на три, остается только три возможных остатка (0, 1 и 2). То, к чему вы стремитесь, это убедиться, что остаток равен 0, следовательно, кратен трем.

Это может быть сделано автоматом с тремя состояниями:

• ST0, кратное 3 (0, 3, 6, 9, ....).
• ST1, кратный 3 плюс 1 (1, 4, 7, 10, ...).
• ST2, кратно 3 плюс 2 (2, 5, 8, 11, ...).

Теперь подумайте о любом неотрицательном числе (это наша область) и умножьте его на два (добавьте двоичный ноль в конец). Переходы для этого:

ST0 -> ST0 (3n * 2 = 3 * 2n, still a multiple of three).
ST1 -> ST2 ((3n+1) * 2 = 3*2n + 2, a multiple of three, plus 2).
ST2 -> ST1 ((3n+2) * 2 = 3*2n + 4 = 3*(2n+1) + 1, a multiple of three, plus 1).

Также подумайте о любом неотрицательном числе, умножьте его на два, затем добавьте одно (добавьте двоичное число в конец). Переходы для этого:

ST0 -> ST1 (3n * 2 + 1 = 3*2n + 1, a multiple of three, plus 1).
ST1 -> ST0 ((3n+1) * 2 + 1 = 3*2n + 2 + 1 = 3*(2n+1), a multiple of three).
ST2 -> ST2 ((3n+2) * 2 + 1 = 3*2n + 4 + 1 = 3*(2n+1) + 2, a multiple of three, plus 2).

Эта идея заключается в том, что в конце вам нужно закончить в состоянии ST0. Однако, учитывая, что может быть произвольное количество подвыражений (и подвыражений), это не легко сводится к регулярному выражению.

Что вам нужно сделать, это разрешить любую из последовательностей перехода, которые могут получить от ST0 до ST0, а затем просто повторить их:

Они сводятся к двум последовательностям RE:

ST0 --> ST0                                      :  0+
    [0]
ST0 --> ST1 (--> ST2 (--> ST2)* --> ST1)* --> ST0:  1(01*0)*1
    [1]     ([0]     ([1]    )* [0]    )* [1]

или регулярное выражение:

(0+|1(01*0)*1)+

Здесь фиксируются кратные три или, по крайней мере, первые десять, которые я тестировал. Вы можете попробовать столько, сколько захотите, они все сработают, в этом вся прелесть математического анализа, а не случайные доказательства.

Answer 3

Ответ (1(01*0)*10*)*, пока единственный, который работает для 110011

Answer 4

Я не думаю, что вы бы. Я не могу поверить ни в один язык, использование регулярного выражения может когда-либо быть лучшим способом сделать это.