我正在研究一个问题（来自Hopcroft、Motwani 和 Ullman的自动机理论、语言和计算机简介0）来编写一个正则表达式，该表达式定义一种由s 和s的所有字符串组成的语言，1不包含 substring 011。
答案(0+1)* - 011正确吗？如果不是，那么正确的答案应该是什么？
问问题
18005 次
2 回答
11
编辑：根据以下评论更新以包括启动状态和修复。
于 2010-04-17T10:58:26.437 回答
5
如果您正在寻找所有没有011作为子字符串的字符串，而不是简单地排除字符串011：
一个经典的正则表达式是：
1*(0+01)*
基本上，您可以在开始时拥有任意数量的数字，但是一旦您达到零，它要么是零，要么是零一（否则你会得到一个零一一）。
一个现代的、不是很常规的正则表达式是：
^((?!011)[01])*$
但是，如果您想要任何不是 的字符串，则011可以简单地枚举短字符串并通配符其余部分：
λ+0+1+00+01+10+11+(1+00+010)(0+1)*
在现代正则表达式中：
^(?!011)[01]*$
于 2010-04-17T10:00:09.210 回答