ВОРОТА | ВОРОТА КС 2021 | Набор 2 | Вопрос 57

Какое из следующих регулярных выражений представляет набор всех двоичных чисел, которые делятся на три? Предположим, что строка ϵ делится на три.
(А) (0+1(01*0)*1)*
(Б) (0+11+10(1+00)*01)*
(С) (0*(1(01*0)*1)*)*
(Г) (0+11+11(1+00)*00)*

Ответ: (А) (Б) (В)
Объяснение: Двоичные числа, которые делятся на 3, делятся на 3 категории:

Числа с двумя последовательными единицами или двумя единицами, разделенными четным числом нулей. Фактически каждая пара «отменяет» себя.
(напр. 11, 110, 1100,1001,10010, 1111)

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

Числа, каждая из которых состоит из трех единиц, разделенных нечетным числом нулей. Эти тройки также «отменяют» себя.
(напр. 10101, 101010, 1010001, 1000101)

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

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

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

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

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

Викторина этого вопроса