18

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

它指出

n 是没有循环的字符串的最长长度。最大的 n 可以是 s，尽管对于某些特定语言它可能更小。

据我了解，如果存在语言 L，那么 L 的泵送长度是识别 L 的有限状态自动机中的状态数量。这是真的吗？

如果是这样，那么上面的最后一行到底是什么意思“尽管对于某些特定语言它可能更小”？我脑子里一团糟。有人可以澄清一下吗？

4

2 回答 2

8

一个州不承认一种语言。DFA 通过完全接受语言中的单词集而不是其他语言来识别语言。DFA 有许多状态。

如果有一个正则语言 L，它可以由 Pumping Lemma 建模，它将有一个属性 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

因此，它由 Pumping Lemma 建模。一个 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 个以上状态的示例（但如果需要，那也可以） .

于 2013-08-24T23:19:15.530 回答
2

我认为一种可能性是当您的 FA 处于无法访问的状态时。FA 有 s 个状态，但是 1 是不可达的，所以所有识别 L 的字符串都将由 (s-1)=n 个状态组成，所以n<s.

于 2013-08-25T00:08:26.667 回答