正则表达式匹配不含“011”子字符串的 0 和 1 字符串

Question

我正在研究一个问题（来自 Hopcroft、Motwani 和 Ullman 的 自动机理论、语言和计算机导论）编写一个正则表达式，定义由

0

和

1

的所有字符串组成的语言不包含子字符串

011

.

答案

(0+1)* - 011

正确吗？如果不是，正确答案应该是什么？

Answer 1

编辑：更新为包括启动状态和修复，如以下评论所示。

Answer 2

如果您正在查找不包含

011

作为子字符串的所有字符串，而不是简单地排除字符串

011

：

一个经典的正则表达式是：

1*(0+01)*

基本上，一开始你可以有任意多个 1，但是一旦你达到 0，后面要么是 0，要么是 0 1（否则你会得到 0 1 1）。

一个现代的、不规则的正则表达式是：

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

---

但是，如果您想要任何不是

011

的字符串，您可以简单地枚举短字符串并使用通配符其余部分：

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

在现代正则表达式中：

^(?!011)[01]*$

Answer 3

这就是正则表达式

0^* ∣1 + 0^* ∣0^* 01 + 0^*