最小化特定的正则表达式

Question

我有以下正则表达式

(1*)+(1*0)(?+11*0)*(11*)

如果最小化，它应该是

(1+01)*

但我无法理解最小化，有人可以解释一下吗？

Answer 1

首先，对于观看此内容的其他人来说，这是传统的正式计算机科学正则表达式，而不是大多数编程语言中使用的正则表达式语言。在编程语言正则表达式术语中，这两个表达式将是1*|1*0(|11*0)*11*和(1|01)*。

现在，问题来了：

1*在两个顶级备选方案中，初始表达式都位于表达式的前面和后面。所以我们可以先把它改写为：

(1*)(?+0(?+11*0)*1)(1*)

现在，一般来说，(?+x)*对于任何正则表达式x只是x*. 所以那是：

(1*)(?+0(11*0)*1)(1*)

现在，也x*与 相同?+xx*，所以我们可以扩展那个内部位：

(1*)(?+0(?+(11*0)(11*0)*)1)(1*)

现在申请a(x+y)b=> axb+ayb：

(1*)(?+01+0(11*0)(11*0)*1)(1*)

现在，申请(xy)*x=> x(yx)*：

(1*)(?+01+0(11*0)1(1*01)*)(1*)

并重新排列括号：

(1*)(?+01+(01)(1*)(01)(1*(01))*)(1*)

并分解出一个共同的前缀：

(1*)(?+(01)(?+(1*(01))(1*(01))*))(1*)

使用我们之前的扩展，但反过来：

(1*)(?+(01)(1*(01))*)(1*)

现在把剩下的带1*进来：

((1*)+(1*)(01)(1*(01))*)(1*)

由于1*与 相同?+1*，我们可以将其写为：

((?+1*)+(1*)(01)(1*(01))*)(1*)

重新排列替代品：

(1*+(?+(1*)(01)(1*(01))*))(1*)

再次应用?+xx*<=>x*等价：

(1*+(1*(01))*)(1*)

现在，x*+(x*y)*可以显示等效于(x+y)*- 应用这里给出：

(1+01)*(1*)

现在我们只应用(x+y)*x*=> (x+y)*，我们就完成了。

(1+01)*

好的，试图找出一个更简单的推导。首先，我需要你接受这些身份，其中x，y，a，和b是任意的正则表达式：

1. (ab)*a <=> a(ba)*

2. xa+ya <=> (x+y)a

3. ?+xx* <=> x*

4. a*(ba*)* <=> (a+b)*

顺便说一句，最后一个标识在构造正则表达式时通常很有用，这些正则表达式可以有效地匹配带有反斜杠转义的字符串等语法([^\\"]|\\.)*，这可能是一种幼稚的方法，但在大多数正则表达式匹配库中使用[^\\"]*(\\.[^\\"]*)*. 无论如何，对于问题：

(1*)+(1*0)(?+11*0)*(11*)

嗯，(?+x)*仍然和 一样x*，所以让我们先这样做：

(1*)+(1*0)(11*0)*(11*)

现在应用身份 2 并将其1*拉出到右侧：

(?+(1*0)(11*0)*1)(1*)

现在，身份 1：

(?+(1*0)1(1*01)*)(1*)

现在为身份 3 做好了准备：

(1*01)*(1*)

身份 1 再次给了我们：

1*((01)1*)*

现在身份 4 给了我们想要的结果：

(1+01)*