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

Question

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

ОБНОВЛЕНИЕ: Хорошо, спасибо всем за вашу помощь, теперь я знаю, как нарисовать NFA, здесь я оставил график и регулярное выражение:

На графике, состояния - это число в базе 10 мод 3.

Например: чтобы перейти в состояние 1, нужно иметь 1, затем вы можете добавить 1 или 0, если вы добавите 1, у вас будет 11 (3 в базе 10), и это число mod 3 равно 0, тогда вы рисуете дугу в состояние 0.

((0*)((11)*)((1((00) *)1) *)(101 *(0|((00) *1 *) *0)1) *(1(000)+1*01)*) *

И другиерегулярное выражение работает, но это короче.

Большое спасибо:)

Answer 1

Я знаю, что это старый вопрос, но эффективный ответ еще не дан, и этот вопрос сначала появляется в Google для бинарного деления на 3 регулярных выражения.

На основе DFA, предложенногоавтор, смехотворно короткое регулярное выражение может быть сгенерировано путем упрощения маршрутов, которые бинарная строка может проходить через DFA.

Самый простой из них, использующий только состояние A:

0*

Включая состояние B:

0*(11)*0*

Включая состояние C:

0*(1(01*0)*1)*0*

И включает в себя тот факт, что после возвращения назадв состоянии A весь процесс может быть запущен снова.

0*((1(01*0)*1)*0*)*

Используя некоторые основные правила регулярных выражений, это упрощается до

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

Хорошего дня.

Answer 2

Если я могу подключить свое решение для этот код вопрос о гольф !Это фрагмент JavaScript, который генерирует регулярные выражения (возможно, неэффективно, но выполняет свою работу) для делимости для каждой базы.

Это то, что он генерирует для делимости на 3 в базе 2:

/^((((0+)?1)(10*1)*0)(0(10*1)*0|1)*(0(10*1)*(1(0+)?))|(((0+)?1)(10*1)*(1(0+)?)|(0(0+)?)))$/

Редактировать: сравнение с Асмором, вероятно очень неэффективно:)

Редактировать 2: Кроме того, это дубликат этоговопрос .

Answer 3

регулярное выражение для двоичных чисел, делимых на 3: (0|1(01*0)*1)*

Answer 4

n + 2n = 3n.Таким образом, 2 смежных бита, установленных в 1, означают кратное 3. Если есть нечетное число смежных 1, это не будет 3.

Так что я бы предложил это регулярное выражение:

(0*(11)?)+