以下正则语言的最小泵送长度

Question

以下是各个语言的最小泵长度：

1. 空语言，p=0，因为该语言没有可泵出的字符串。
2. (01)*，p=2，因为01是可以被泵出的最短字符串。
3. 10(11*0)*0，p=5，因为10100是可以被泵出的最短字符串。
4. 1011，p=0，因为该字符串无法进行泵操作。
5. 011 U 0*1*，p=1，因为字符串0可以被泵出。

作者不确定自己的答案是否正确，欢迎任何帮助和指正。非常感谢！

- user2293062

---

这可能更适合发表在 计算机科学StackExchange 上。 - Kyll

Answer 1

我认为Simon的回答可能有点偏离。事实上，你需要在某个地方进行一个循环。Pumping Lemma要求识别字符串所采取的路径包括一个循环（这就是Pumping Lemma中“xyz”中的“y”）。我们可以无限次数地采用这个循环，从而增加字符串。

1. 应该是1。即使语言中没有字符串，最小泵浦长度也必须始终大于0。
2. 应该是2。如果p = 1，则我们无法进行01泵浦（因为y必须等于0，而001不属于该语言）。
3. 应该是5。
4. 这也应该是5。如果我们设置p = 4，则声称“1011”是可泵的（但它不是，因为它是该语言中唯一的字符串）。
5. p = 1。

- Alec Brickner

Answer 2

根据Patrick87的说法，最小泵长度是指在最小化DFA时可以进行的最大转换次数，而不需要重复访问某些状态。因此，该过程变为将您的正则表达式转换为NFA，将NFA转换为DFA，最小化DFA并计算沿有向边的最长路径，而不会重复访问相同的状态。有关此转换和最小化的介绍，请参见Torben Mogensen的免费书籍编译器设计基础第2.6、2.8章节。

根据这个定义，

1. p = 0，因为空语言的最小化DFA中没有转换。
2. p = 1。对于(01)*的最小化DFA有两个状态，只能进行一次转换而不会到达初始接受状态。
3. p = 3。对于10(11*0)*0的最小化DFA将有一个状态需要被访问两次才能使子表达式(11*0)*成为推导的一部分。
4. p = 4。对于1011的最小化DFA恰好有4条边且没有递归。
5. p = 1。语言011是语言0*1*的子集，因此011 U 0*1* = 0*1*。并且既然0和1都不能被泵出，只能跟随一个非递归边。

- sshine