抽吸引理中的「抽吸長度」究竟是什麼？

我想了解這個'神奇'數字'n'是什麼用於抽水引理的每個應用程序。之後關於這個問題的研究小時，我來到了以下網址：http://elvis.rowan.edu/~nlt/TheoryNotes/PumpingLemma.pdf 抽吸引理中的「抽吸長度」究竟是什麼？

它指出

n是最長的一個字符串可以是不具有環。最大的n可以是s，但對某些特定的語言來說它可能更小。

根據我的理解，如果有語言L，那麼L的抽運長度就是有限狀態自動機中識別L的狀態量。這是真的嗎？

如果是，那麼上面的最後一行究竟是什麼意思，「儘管它對於某種特定的語言可能會更小」？我腦子裏一團糟。請問有人能清理它嗎？

來源

2013-08-24 Ivan Prodanov

狀態不識別語言。 DFA通過準確接受語言中的單詞集而不承認其他語言來識別語言。 DFA有許多州。

如果有一個正常語言L，可以通過Pumping引理來模擬，它將有一個屬性n。

對於具有s狀態的DFA，爲了使其接受L，s必須> = n。

最後一行只是說有些語言中s大於n，而不是相等。

這可能更適合於https://cstheory.stackexchange.com/或https://cs.stackexchange.com/（不太確定我自己的價值）。

注意：中平凡，並不是所有的DFA的足夠的狀態將接受的語言。另外，語言通過抽象引理這一事實並不意味着它是常規的（但是如果失敗則意味着它不是）。

還要注意，FA和DFA之間的語言變化 - 這有點鬆懈，但由於NDFA具有與DFA相同的功能，並且DFA更易於編寫和理解，所以使用DFA作爲證明。

編輯我給一個正規語言的例子，所以你可以看到ü的想法，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個以上的狀態來構建一個狀態（但如果需要的話也可以）。

來源

2013-08-24 23:19:15

狀態2可以在y上自行循環，並轉到狀態3作爲z上的接受狀態。因此，只需要3個狀態 – Ion

@Ion：3狀態DFA也接受不屬於滯後語言的'xyz'。 –

你能改變你的符號嗎？你在不同的上下文中使用n（「n> 2 ... n = 4」），z（「w = z」，「| z | = 3」，也暗示是z = xyyz）混亂。 –

我想有一種可能性是當你有一個不可達狀態的FA。FA有s狀態，但是1無法到達，所以識別L的所有字符串將由（s-1）= n個狀態組成，所以n<s。

來源

2013-08-25 00:08:26 chiliNUT

呃，我認爲它忽略了無法訪問的狀態，因爲在沒有這個限制的情況下製作一個任意大的DFA是微不足道的 –

同意，完全無關緊要，只是把它放在那裏作爲一種可能:) – chiliNUT

抽吸引理中的「抽吸長度」究竟是什麼？

回答

相關問題