regular-language - 常规语言的最小泵送长度

Question

如何计算常规语言的最小抽水长度。例如，如果我有 0001*，那么最小抽气长度应该是 4，即 000 无法抽气。为什么会这样？

Answer 1

它将小于或等于该语言的最小 DFA 中的状态数减去一。因此，将正则表达式转换为 DFA，将其最小化，并计算状态。对于您的示例:

0001*

SOURCE    SYMBOL    DESTINATION
q1        0         q2
q1        1         q5
q2        0         q3
q2        1         q5
q3        0         q4
q3        1         q5
q4        0         q5
q4        1         q4
q5        0         q5
q5        1         q5

为什么等于这个？因为这是您可以在 DFA 中进行的最大转换次数，而无需两次访问某个状态。一旦你访问一个州两次，你就循环了。

当然，语言的最小 DFA 可能缺少该长度的路径。在这种情况下，您可以通过使用诸如自动机图形的深度优先搜索之类的方法并查看可以跟踪多长的路径，找到不会两次访问某个状态的最长路径(从起始状态开始)。那将是你真正的答案。