Pumping引理中的"泵送长度"究竟是什么？

Question

我试图理解在Pumping引理的每个应用中使用的这个"神奇"数字'n'是什么.经过几个小时的研究,我来到了以下网站:http://elvis.rowan.edu/~nlt/TheoryNotes/PumpingLemma.pdf

它指出

n是最长的字符串,没有循环.最大的n可以是s,但对某些特定语言来说可能更小.

根据我的理解,如果有一个语言L,那么L的泵浦长度是有限状态自动机中识别L的状态量.这是真的吗？

如果是,那么上面的最后一行究竟是什么意思"虽然某些特定语言可能会更小"？在我脑海里乱七八糟.有人可以把它弄清楚吗？

Answer 1

一个州不承认一种语言.DFA通过接受语言中的单词集而不是其他单词来识别语言.DFA有很多州.

如果存在可以通过抽取引理建模的常规语言L,则它将具有属性n.

对于具有s状态的DFA,为了使其接受L,s必须> = n.

最后一行仅表明存在一些语言,其中s大于n,而不是相等.

这可能更适合https://cstheory.stackexchange.com/或https://cs.stackexchange.com/(不太确定我自己的价值).

注意:通常情况下,并非所有具有足够状态的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个状态的那个(但如果需要的话,那就没关系) .