以下常规语言的最小抽水长度

Question

以下语言的最小抽水长度是多少？

1. 空语
2. (01)*
3. 10(11*0)*0
4. 1011
5. 011 ü 0*1*

这是我的解决方案.如果我错了,请纠正我.

1. p = 0,因为该语言没有可泵送的字符串
2. p = 2因为01是可以泵送的最短字符串
3. p = 5因为10100是可以泵送的最短字符串
4. p = 0,因为不能抽出字符串
5. p = 1,因为0可以泵送字符串

我不确定我的答案,所以任何帮助都表示赞赏.非常感谢!

Answer 1

我认为西蒙的回答可能有些偏差.事实上,你需要在某个地方采取循环.泵浦引理要求识别弦的路径包括一个循环(这是泵浦引理'xyz'的'y').我们可以根据需要多次使用这个循环,这可以抽出字符串.

1. 这应该是1.即使语言中没有字符串,最小抽吸长度也必须始终大于0.
2. 这应该是2.如果p = 1,我们不能泵01(因为y必须等于0,而001不在语言中).
3. 这应该是5.
4. 这也应该是5.如果我们设置p = 4,那么我们声称"1011"是可泵送的(它不是,因为它是该语言中唯一的字符串).
5. p = 1.

Answer 2

根据Patrick87 的说法，最小泵送长度定义为在最小化 DFA 中无需访问某个状态两次即可进行的最大转换次数。然后，该过程将正则表达式转换为 NFA，将 NFA 转换为 DFA，最小化 DFA 并计算沿有向边的最长路径，而无需两次访问相同的状态。有关此转换和最小化的介绍，请参阅 Torben Mogensen 的免费书籍《编译器设计基础》第 2.6、2.8 章。

根据这个定义，

1. p = 0，因为空语言的最小化 DFA 中没有转换。
2. p = 1。最小化的 DFA(01)*有两种状态，并且您只能进行一次转换，而不会以初始接受状态结束。
3. p = 3。最小化的 DFA for10(11*0)*0将具有必须访问两次才能使子表达式(11*0)*成为推导的一部分的状态。
4. p = 4。 的最小化 DFA1011恰好有 4 个边并且没有递归。
5. p = 1。该语言011是语言 的子集0*1*，因此011U 0*1*= 0*1*。并且由于0或都不1能被泵送，因此只能遵循一个非递归边缘。