Регулярное выражение для соответствия строки 0 и 1 без подстроки '011'

Question

Я работаю над проблемой (из Введение в теорию автоматов, языков и компьютеров Хопкрофта, Мотвани и Уллмана), чтобы написать регулярное выражение, определяющее язык, состоящий из всех строк 0 s и 1 s, не содержащие подстроку 011.

Является ли ответ (0+1)* - 011 правильным? Если нет, какой должен быть правильный ответ для этого?

Answer 1

Изменить: Обновлено, чтобы включить стартовые состояния и исправления, как показано ниже комментарии.

Answer 2

Если вы ищете все строки, которые не имеют 011 в качестве подстроки, а не просто исключают строку 011:

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

1*(0+01)*

Как правило, в начале вы можете иметь столько единиц, сколько захотите, но как только вы достигнете нуля, за ним последуют либо нули, либо нули (так как в противном случае вы получите ноль один один) .

Современное, не совсем регулярное регулярное выражение будет:

^((?!011)[01])*$

---

Если, однако, вам нужна любая строка, отличная от 011, вы можете просто перечислить короткую строку и подстановить остальные символы:

λ+0+1+00+01+10+11+(1+00+010)(0+1)*

А в современном регулярном выражении:

^(?!011)[01]*$