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

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



Я знаю, что есть небольшое правило, чтобы выяснить, если двоичное число делится на 3: Возьмите число единиц в четные места в цифре и вычесть на число единиц в нечетных местах в цифре - если это равно нулю, то число делится на 3 (Пример: 110-1 в четном слоте 2 и 1 в нечетном слоте 1). Однако у меня возникли некоторые проблемы с адаптацией этого к регулярному выражению.



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

1700   4  

4 ответов:

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

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

Начальная ДФА

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

Исправлена DFA

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

Преобразование в практическое регулярное выражение в ароматизаторах, поддерживающих рекурсивное регулярное выражение, можно легко сделать, когда у вас есть DFA. Это показано для случая (основания b = 10, d = 710) в этот вопрос из 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>)
Разбив его, вы можете увидеть, как он построен. Группировка atomic (или non-backtracking group, или группа, которая ведет себя собственнически), используется для проверки соответствия только пустой Строковой альтернативы. Это трюк для эмуляции (?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>)
8  
2017-05-23 15:09:49

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

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

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

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

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

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

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

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

3  
2018-02-14 01:32:31

Проблема, с которой вы сталкиваетесь, заключается в том, что, хотя ваш трюк (вероятно) действителен, он не соответствует практическому 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]. Это описание кажется вам знакомым?
1  
2013-03-11 04:12:41

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

  1. числа с двумя последовательными 1 или двумя 1, разделенными четным числом 0. фактически каждая пара "аннулирует"себя.

(напр. 11, 110, 1100,1001,10010, 1111)

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

  1. числа с тремя 1, разделенными нечетным числом 0. Эти триплеты также "отменяют" себя.

(напр. 10101, 101010, 1010001, 1000101)

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

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

(напр. 1010111, 1110101, 1011100110001)

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

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

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

Как его читать:

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

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

/ указывает на выбор вариантов с обеих сторон в скобках

0  
2016-11-10 04:55:17

Comments

    Ничего не найдено.
Click here to cancel reply.