Регулярное выражение для двоичных чисел, делящихся на 3

Следуя тому, что говорит Оли Чарльзуорт, вы можете построить DFA для делимости числа по основанию b на определенный делитель d, где состояния в DFA представляют остаток от деления.

Для вашего случая (база 2 - двоичное число, делитель d = 3₁₀):

Обратите внимание, что приведенный выше DFA принимает пустую строку как «число», кратное 3. Это можно легко исправить, добавив еще одно промежуточное состояние впереди:

Преобразование в теоретическое регулярное выражение можно выполнить с помощью обычного процесса.

Преобразование в практическое регулярное выражение в вариантах, поддерживающих рекурсивное регулярное выражение, может быть легко выполнено, если у вас есть DFA. Это показано для случая (база b = 10, d = 7₁₀) в этот вопрос от CodeGolf.SE.

Позвольте мне процитировать регулярное выражение в ответе Lowjacker, написанный в стиле регулярных выражений Ruby:

(?!$)(?>(|(?<B>4\g<A>|5\g<B>|6\g<C>|[07]\g<D>|[18]\g<E>|[29]\g<F>|3\g<G>))(|(?<C>[18]\g<A>|[29]\g<B>|3\g<C>|4\g<D>|5\g<E>|6\g<F>|[07]\g<G>))(|(?<D>5\g<A>|6\g<B>|[07]\g<C>|[18]\g<D>|[29]\g<E>|3\g<F>|4\g<G>))(|(?<E>[29]\g<A>|3\g<B>|4\g<C>|5\g<D>|6\g<E>|[07]\g<F>|[18]\g<G>))(|(?<F>6\g<A>|[07]\g<B>|[18]\g<C>|[29]\g<D>|3\g<E>|4\g<F>|5\g<G>))(|(?<G>3\g<A>|4\g<B>|5\g<C>|6\g<D>|[07]\g<E>|[18]\g<F>|[29]\g<G>)))(?<A>$|[07]\g<A>|[18]\g<B>|[29]\g<C>|3\g<D>|4\g<E>|5\g<F>|6\g<G>)

Разобрав его, вы увидите, как он устроен. атомарная группировка (или группа без возврата, или группа, которая ведет себя притяжательно) используется, чтобы гарантировать соответствие только альтернативе пустой строки. . Это трюк для эмуляции (?DEFINE) в Perl. Затем группы с A по G соответствуют остатку от 0 до 6, когда число делится на 7.

(?!$)
(?>
  (|(?<B>4   \g<A>|5   \g<B>|6   \g<C>|[07]\g<D>|[18]\g<E>|[29]\g<F>|3   \g<G>))
  (|(?<C>[18]\g<A>|[29]\g<B>|3   \g<C>|4   \g<D>|5   \g<E>|6   \g<F>|[07]\g<G>))
  (|(?<D>5   \g<A>|6   \g<B>|[07]\g<C>|[18]\g<D>|[29]\g<E>|3   \g<F>|4   \g<G>))
  (|(?<E>[29]\g<A>|3   \g<B>|4   \g<C>|5   \g<D>|6   \g<E>|[07]\g<F>|[18]\g<G>))
  (|(?<F>6   \g<A>|[07]\g<B>|[18]\g<C>|[29]\g<D>|3   \g<E>|4   \g<F>|5   \g<G>))
  (|(?<G>3   \g<A>|4   \g<B>|5   \g<C>|6   \g<D>|[07]\g<E>|[18]\g<F>|[29]\g<G>))
)
(?<A>$|  [07]\g<A>|[18]\g<B>|[29]\g<C>|3   \g<D>|4   \g<E>|5   \g<F>|6   \g<G>)

У меня есть другой способ решения этой проблемы, и я думаю, что это легче понять. Когда мы делим число на 3, у нас может быть три остатка: 0, 1, 2. Мы можем описать число, которое делится на 3, используя выражение 3t (t — натуральное число).

Когда мы добавляем 0 после двоичного числа, остаток которого равен 0, фактическое десятичное число будет удвоено. Потому что каждая цифра перемещается на более высокую позицию. 3t * 2 = 6t, это тоже делится на 3.

Когда мы добавляем 1 после двоичного числа, остаток которого равен 0, фактическое десятичное число будет удвоено плюс 1. Поскольку каждая цифра перемещается на более высокую позицию, за которой следует 1; 3t * 2 + 1 = 6t + 1, остаток равен 1.

Когда мы добавляем 1 после двоичного числа, остаток которого равен 1. Фактическое десятичное число будет удвоено плюс один, а остаток равен 0; (3t + 1)*2 + 1 = 6t + 3 = 3(2t + 1), это делится на 3.

Когда мы добавляем 0 после двоичного числа, остаток которого равен 1. Фактическое десятичное число будет удвоено. А остаток будет 2. (3t + 1)*2 = 6t + 2.

Когда мы добавляем 0 после двоичного числа, остаток которого равен 2. Остаток будет равен 1. (3t + 2)*2 = 6t + 4 = 3(2t + 1) + 1

Когда мы добавляем 1 после двоичного числа, остаток которого равен 2. Тогда остаток все равно будет 2. (3t + 2)*2 + 1 = 6t + 5 = 3(2t + 1) + 2.

Независимо от того, сколько единиц вы прибавите к двоичному числу, остаток которого равен 2, остаток всегда будет равен 2. (3(2t + 1) + 2)*2 + 1 = 3(4t + 2) + 5 = 3(4t + 3) + 2

Таким образом, у нас может быть DFA для описания двоичного числа:

Примечание. Край q2 -> q1 должен быть помечен 0.

Двоичные числа, делящиеся на 3, делятся на 3 категории:

1. Числа с двумя последовательными единицами или двумя единицами, разделенными четным числом нулей. Фактически каждая пара «отменяет» себя.

(ex. 11, 110, 1100,1001,10010, 1111)

(десятичные: 3, 6, 12, 9, 18, 15)

2. Числа с тремя единицами, разделенными нечетным числом нулей. Эти тройки также «отменяют» себя.

(ex. 10101, 101010, 1010001, 1000101)

(десятичные: 21, 42, 81, 69)

3. Некоторая комбинация первых двух правил (в том числе внутри друг друга)

(ex. 1010111, 1110101, 1011100110001)

(десятичное число: 87, 117, 5937)

Таким образом, регулярное выражение, учитывающее эти три правила, выглядит просто:

0*(1(00)*10*|10(00)*1(00)*(11)*0(00)*10*)*0*

Как читать:

() инкапсулировать

* означает, что предыдущий номер/группа необязательны

| указывает на выбор опций с обеих сторон в круглых скобках

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

Альтернативный подход состоит в том, чтобы отметить, что (работая от MSB к LSB) после i-го символа x[i] ваша подстрока должна быть равна 0, 1 или 2 в арифметике по модулю-3; назовите это значение S[i]. x[i+1] должно быть либо 0, либо 1, что эквивалентно умножению на 2 и дополнительному добавлению 1.

Итак, если вы знаете S[i] и x[i+1], вы можете вычислить S[i+1]. Это описание звучит знакомо?