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

Question

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

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

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

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

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

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

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

Answer 1

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

Спойлер (парение над ним для решения):

Подсказка 1:

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

Подсказка 2:

Это означает, что между каждым 0 -значное есть максимум 2 из 1 -digits.

Подсказка 3:

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

Решение:

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