Как бы вы написать регулярное выражение для определения всех строк 0 и 1. что, в виде двоичного числа, представляют собой целое число, кратное 3.Регулярного выражения для определения некоторой двоичной последовательности
Некоторых действительных двоичных чисел будут be:
11 110 1001 1100 1111
Используя DFA here, мы можем сделать регулярное выражение следующим образом, где 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
+1. Теперь это здорово. Я понятия не имел, что вы можете создать регулярное выражение, которое легко от DFA. –
Спасибо за мастер-класс. Я думаю, что я не стану отмечать эту задачу на Codewars как завершенную, так как я бы не сделал это сам. – Minras
Я не думаю, что вы бы это сделали. Я не могу поверить в какой-либо язык, используя регулярное выражение, которое когда-либо могло быть лучшим способом сделать это.
Я знаю, что это не лучший способ. Я знаю, что это можно сделать, но я просто не могу понять, как это сделать. Он включает в себя рисование автоматов и устранение средних состояний. – Jaelebi
@Dave Webb, вы можете определенно сделать это. На самом деле, это довольно распространенный вид упражнений в курсе теории CS, поэтому я не решаюсь ответить на этот вопрос. – BobbyShaftoe
Знаете ли вы, как это можно сделать? любые подсказки? – Jaelebi
При делении числа на три, существует только три возможных остатка (0, 1 и 2). То, что вы намереваетесь, состоит в том, чтобы гарантировать, что остаток равен 0, следовательно, кратно трем.
Это может быть сделано с помощью автомата с тремя состояниями:
Теперь подумайте о любого неотрицательного числа (это наш домен) и умножить его на два (галс двоичный ноль на конце). Переходы для этого являются:
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 затем просто повторить их:
Они сводятся к двум РЗ последовательности:
ST0 --> ST0 : 0+
[0]
ST0 --> ST1 (--> ST2 (--> ST2)* --> ST1)* --> ST0: 1(01*0)*1
[1] ([0] ([1] )* [0] )* [1]
или regex:
(0+|1(01*0)*1)+
Это фиксирует кратные три или, по крайней мере, первую десятку, которую я тестировал.Вы можете попробовать сколько угодно, они все будут работать, это красота математического анализа, а не анекдотические доказательства.
Ответ (1(01*0)*10*)*, который является единственной до сих пор, что работает для 110011
Является ли это ваше вычислительная теория домашнего задания? – BobbyShaftoe
Возможно, вы могли бы дать некоторый фон, как вы хотите, и какой язык вы хотите использовать. –
часть его. я думаю, что у меня есть правильная NFA, но, похоже, не справляется со средними шагами, поскольку это довольно сложно. – Jaelebi