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）。