Reg语言的抽样引理定理的哪一部分指示我是否正在抽入或抽出以及我抽入/抽出多少次？

Question

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

Answer 1

正规语言的抽象引理对于正规语言的规则性来说是一个必要的条件，尽管不是充分的条件。如果L是一个正则语言，然后有一个自然数p使得任何字符串s的长度至少p可以被写入S = xyz，其中：

• y具有长度的至少一个;
• 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本身;我们已经假设s在第3行假设的L中。无论你是“抽入”还是“抽出”，取决于你选择的n。

泵浦引理正规语言的工作原理是这样的逻辑：

1. 如果语言是有规律的，有它的最小DFA。
2. 如果该语言的最小DFA具有p个状态，则长度为p或更大的语言中的任何字符串都必须导致DFA多次访问某个状态（鸽主原则）。
3. 如果DFA多次访问某个状态，则DFA中会出现一个循环，并且此字符串会导致DFA对其进行遍历。
4. 如果这个字符串，这引起了DFA循环若干次，是L，那么还有其他的字符串，其循环各地旅行次或更少的时间也必须在L.

鉴于这种逻辑：

1. p激发态的=假想数以最小DFA对于L
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）。