Создайте регулярное выражение для соответствия следующему языку

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

Предоставленный алфавит является двоичным {0, 1}

Определение языка довольно неформальное:

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

Таким образом, примерами строк, соответствующих этому определению, будут 000, 001, 1010 и так далее.

Моя проблема заключается в том, чтобы найти регулярное выражение, соответствующее этому определению языка. Я пытался поиграться с http://regexr.com/, но обнаружил, что "..0" соответствует только каждые три символов с нулем в конце. Я не уверен, как сопоставить каждую подстроку в том, как определен язык, или если это вообще возможно.

Есть ли способ построить регулярное выражение для этой проблемы?


regex deterministic finite-automata
person JavascriptLoser    schedule 03.10.2016    source источник

Ответы (1)


arrow_upward
3
arrow_downward

Требуется нестандартное мышление. Не реализуйте регулярное выражение для определения неформального языка, но для свойства, которое подразумевает это определение.

Спойлер (наведите на него курсор для решения):

Подсказка 1:

Если любая произвольная подстрока длиной 3 должна иметь 0-цифру, то невозможно иметь 3 цифры в строке, которые являются 1-цифрами.

Подсказка 2:

Это означает, что между каждой 0-цифрой находится не более 2 из 1-цифр.

Подсказка 3:

Это делает его языком, в котором после 0-2 1-цифр идет, возможно, бесконечное количество групп, состоящих из 0-цифр и 0-2 1-цифр.

Решение:

^1{0,2}(01{0,2})*$, или эквивалентно и более математически, ^(11?)?(0(11?)?)*$

person Amadan    schedule 03.10.2016
comment
Это здорово, спасибо. Как можно было бы расширить это регулярное выражение, если бы алфавит теперь содержал цифру 2, а неформальный язык не изменился? - person JavascriptLoser; 03.10.2016
comment
Перечитайте подсказки, замените 1 на 1 или 2. Что-то перестает иметь смысл? (Это задание: чем больше вы пробуете себя, тем большему учитесь.) - person Amadan; 03.10.2016
comment
Логика подсказок имеет смысл, но я понятия не имею, как представить 1 или 2 в виде шаблона регулярного выражения. - person JavascriptLoser; 03.10.2016
comment
Типичное регулярное выражение: [12]. Точнее, (1|2). - person Amadan; 03.10.2016
comment
Я попробовал ^[1(1|2)]{0,2}(0[1(1|2)]{0,2})*$ и, кажется, у меня получилось! Просто из любопытства для регулярного выражения, есть ли способ сопоставить ровно один ноль за 3 символа, а не хотя бы один ноль? - person JavascriptLoser; 03.10.2016
comment
Не совсем. Это должно было быть или-или. Например, ваше регулярное выражение также будет соответствовать 01000(00|1. Правильным будет ^[12]{0,2}(0[12]{0,2})*$ (больше программирования) или ^((1|2)(1|2)?)?(0((1|2)(1|2)?)?)*$ (больше теории автоматов). Что касается вашего другого вопроса, перечитайте подсказки, так как я думаю, что вы все еще не поняли решение. Я не сопоставляю хотя бы один ноль на три символа, я ограничиваю количество ненулевых знаков между двумя нулями не более чем двумя. Это расщепление семантики, но в программировании нужно быть придирчивым. - person Amadan; 03.10.2016
comment
Если вы хотите иметь ровно один ноль на каждые три символа, то нули должны быть ровно на каждой третьей позиции: ^1{0,2}(011)*01{0,2}$. - person Amadan; 03.10.2016