[理工] 計理pumping lemma問題

[usha9comeon (usha9comeon)]

大家好，

小妹最近在寫計理遇到一個問題，

因為 pumping lemma 的假設是以DFA來做，

| w | >= M （DFA state 數量）

那如果這個假設改成“NFA“的話可以嗎？

因為爬過很多文發現沒有看到類似問題，

甚至看到有網站解釋pumping lemma就是用NFA，

不過印象中以前上課是說不行的，

所以上來詢問原因，

謝謝大家。



-----
Sent from JPTT on my OPPO A1601.

--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 180.217.201.140
※ 文章網址: https://www.ptt.cc/bbs/Grad-ProbAsk/M.1511709774.A.957.html
推 alan23273850: 我以前上課是用DFA證明的，不妨列一下網站？
https://www.zhihu.com/question/29410851
裡面有個回答用NFA做了pumping lemma
※ 編輯: usha9comeon (180.217.201.140), 11/27/2017 01:03:50
→ alan23273850: 這個問題真的很好，讓我想了好久，先來個不負責任簡
→ alan23273850: 答，我覺得可以。
→ alan23273850: 先回想一下pumping lemma內容，大意是說給定一個無
→ alan23273850: 限大的Regular language，至少要有一個DFA或NFA能產
→ alan23273850: 生它，而這台自動機，根據鴿籠原理，一定會有以下特
→ alan23273850: 性：只要長度大於m的字串，就一定要有其中一節能持
→ alan23273850: 續的pumping出來而仍在language中，但是滿足這樣的
→ alan23273850: 特性並不代表就真的找到DFA或NFA，因此實務上通常是
→ alan23273850: 用反證法。
→ alan23273850: 那現在反過來問樓主，你覺得當我不論m的門檻設多少
→ alan23273850: 都一定會有個無法順利pumping的老鼠屎字串，這樣子
→ alan23273850: 是找不到DFA還是NFA呢？要注意的是，DFA和NFA所能生
→ alan23273850: 成的language能力是等價的，這才是我覺得這個問題很
→ alan23273850: 難回答的原因，詳細的解釋就等樓下補充吧XD
推 FRAXIS: 應該是 DFA 和 NFA 都找不到..