我试图了解在 Pumping 引理的每个应用程序中使用的这个“神奇”数字“n”是什么。经过几个小时的研究，我来到了以下网站:http://elvis.rowan.edu/~nlt/TheoryNotes/PumpingLemma.pdf
它指出
n is the longest a string can be without having a loop. The biggest n can be is s, though it might be smaller for some particular language.
据我了解，如果存在语言 L，那么 L 的泵送长度是识别 L 的有限状态自动机中的状态数量。这是真的吗？
如果是这样，那么上面的最后一行究竟是什么意思“尽管对于某些特定语言来说它可能更小”？我脑子里一团糟。有大佬能解一下吗？
最佳答案
一个国家不承认一种语言。 DFA 通过完全接受语言中的单词集而不接受其他语言来识别语言。 DFA 有许多状态。
如果存在可以通过泵引理建模的正则语言 L，它将具有属性 n。
对于具有 s 个状态的 DFA，为了接受 L，s 必须 >= n。
最后一行仅说明在某些语言中 s 大于 n，而不是相等。
这可能更适合 https://cstheory.stackexchange.com/或 https://cs.stackexchange.com/ (不太确定我自己的值(value))。
备注 : 简单地说，并非所有具有足够状态的 DFA 都会接受该语言。此外，语言通过抽水引理这一事实并不意味着它是规则的(但失败意味着绝对不是)。
另请注意，FA 和 DFA 之间的语言变化 - 这有点松懈，但由于 NDFA 与 DFA 具有相同的功能，而且 DFA 更易于编写和理解，因此使用 DFA 进行证明。
编辑 我将举一个常规语言的例子，这样你就可以看到 u、v、w、z 和 n 的概念。然后我们将讨论 s。
L = xy^nz, n > 2 (i.e. xyyz, xyyyz, xyyyyz)
u = xy
v = y
w = z
n = 4
因此:
|z| = 3: xyz (i = 0) Not in L, but |z| < n
|z| = 4: xyyz (i = 1)
|z| = 5: xyyyz (i = 2)
etc
因此，它由泵引理建模。 DFA 至少需要 4 个状态。所以让我们想一个。
-> State 1: x
State 1:
-> State 2: y
State 2:
-> State 3: y
State 3:
-> State 3: y
-> State 4: z
State 4:
Accepting state
Terminating state
4 个状态，正如预期的那样。不可能像 n = 4 所预期的那样用更少的时间来完成。在这种情况下，这个例子非常简单，所以我认为你不能构建一个具有超过 4 个状态的状态(但如果需要的话也可以) .
关于automata - Pumping 引理中的 'pumping length' 到底是什么？，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/18423903/