Регулярное выражение к строке совпадения 0 и 1's без '011' подстрока
Я работаю над проблемой (от Введения до Теории автоматов, Языков и Компьютера Hopcroft, Motwani и Ullman) для записи регулярного выражения, которое определяет язык, состоящий из всех строк 0s и 1s не содержащий подстроку 011.
Ответ (0+1)* - 011 корректный? Если не, каков должен быть корректный ответ для этого?
2 ответа
Редактировать: Обновлено, чтобы включить начальные состояния и исправления, как указано в комментариях ниже.
Если вы ищете все строки, которые не содержат 011 в качестве подстроки, а не просто исключаете строку 011 :
Классическое регулярное выражение для этого будет:
1*(0+01)*
В основном вы в начале может быть столько единиц, сколько вы хотите, но как только вы достигнете нуля, следуют либо нули, либо ноль-единицы (иначе вы бы получили ноль-один-один).
Современное, не совсем обычное регулярное выражение будет выглядеть следующим образом:
^((?!011)[01])*$
ЕСЛИ, однако, вам нужна любая строка, отличная от 011 , вы можете просто перечислить короткие строки и использовать подстановочные знаки для остальных:
λ+0+1+00+01+10+11+(1+00+010)(0+1)*
И в современном регулярном выражении:
^(?!011)[01]*$