0

考试即将到来，教授希望包括这些信息。我了解引理是如何工作的，但我无法概念化“泵送”是如何发生在进出和多少次方面的。

4

1 回答 1

0

正则语言的泵引理是形式语言正则性的必要条件，但不是充分条件。如果 L 是常规语言，则存在一个自然数 p，使得任何长度至少为 p 的字符串 s 都可以写成 s = xyz，其中：

  • y 的长度至少为 1；
  • xy 的长度不大于 p；
  • 对于任何自然数 n，x(y^n)p 也在 L 中。

从逻辑上讲，条件是：

1. if (L is regular) then
2.  there exists a natural number p such that
3.      if s is in L and |s| >= p then
4.          s = xyz
5.          and |y| > 0
6.          and |xy| <= p
7.          and x(y^n)z is in L

在第 7 行，我们说字符串 s 的“泵送”版本必须在 L 中。请注意，对于 n = 1，我们恢复 s 本身；我们已经通过第 3 行中的假设假设 s 在 L 中。您是“抽入”还是“抽出”，以及抽出多少，取决于您对 n 的选择。

常规语言的抽水引理按以下逻辑工作：

  1. 如果一种语言是常规语言，则它的 DFA 最小。
  2. 如果该语言的最小 DFA 具有 p 个状态，则长度为 p 或更大的语言中的任何字符串都必须导致 DFA 多次访问某个状态（鸽巢原理）。
  3. 如果 DFA 多次访问一个状态，则 DFA 中存在一个循环，该字符串导致 DFA 遍历它。
  4. 如果这个导致 DFA 循环若干次的字符串在 L 中，那么还有其他字符串在循环中传播的次数更多或更少，它们也必须在 L 中。

鉴于此逻辑：

  1. p = L 的最小 DFA 中的假设状态数
  2. x = 执行某个循环之前的输入字符串部分
  3. y = 代表一个执行循环的输入字符串部分
  4. z = 执行某个循环后的输入字符串部分

例如，考虑这个最小 DFA：

        0,1      0     /---\
--->(q0)--->(q1)--->(q2)<--/ 0,1
     ^       |
      \------/ 
          1

字符串 0100 在 L.p = 3 和 |0100| 中。= 4，所以泵引理必须成立。我们对 x、y 和 z 的唯一选择是 x=0、y=10 和 z=0。抽水引理声称我们可以去掉 y 或向其添加任意数量的倍数并在 L 中得到另一个字符串。我们看到这是可行的，因为 y 只是从 q1 到 q0 的循环；我们可以跳过它（n = 0）或者我们可以重复它（n > 1）。

于 2017-10-02T18:47:27.450 回答