pumping-lemma - 为什么字符串的数量应该大于或等于泵引理中的状态数？

Question

如果L是正则语言，则存在一个常数n（取决于L），使得对于w语言中的每个字符串L，使得 的长度w大于或等于n，我们可以w分成三个字符串，w = xyz。

w = length of string. n = Number of States.

为什么要选择w大于或等于n？什么是泵送长度？

Answer 1

如果您查看引理的完整陈述（http://en.wikipedia.org/wiki/Pumping_lemma_for_regular_languages），您会发现它实际上是在说明每个字符串都由前缀x组成，该部分可以重复任何次数y和后缀z。现在很明显，在最短的情况下（当重复部分只取一次时），长度w等于语言所需的状态数。这张维基百科图片非常有用：

http://en.wikipedia.org/wiki/File:Pumping-引理_xyz_svg.svg

Answer 2

您似乎误解了引理（您也没有完全说明），并将证明的各个方面与您所做的陈述混合在一起。引理说，对于每一种常规语言L，都有一个常数，使得属于p的每个至少包含符号的字符串都有一个长度不大于可以“泵送”的非空子字符串，总是产生 的另一个元素。常数是（a）“泵送长度”。pLpLp

这可以通过观察如果一种语言是规则的，那么有一个有限状态自动机接受它，并取p为该自动机中的状态数（细节省略）来证明。

然而，这并不意味着识别给定常规语言的最小 FSA 中的状态数是该语言可能的最小泵送长度。例如，考虑由 { an} 和 { bn} 的并集组成的语言 all n。您需要一个四态 FSA 来识别这种语言，但它的最小泵送长度为 1。