有K個狀態的NFA接受字符串的長度<= k

Question

是否有可能構造一個N狀態，其中k個狀態可識別所有長度爲< = k的字符串並拒絕長度大於k的所有字符串？

Answer 1

否。證明是通過k的數學歸納。

基準案例：對於k = 0，一個零狀態的NFA可能不是一個有效的對象，當然也不能說是接受任何東西。編輯：也許值得加k = 1以及，因爲k = 0的情況是異常的。對於k = 1，狀態不接受（在這種情況下，接受的語言是空的），或者它正在接受，在這種情況下，它只識別空字符串（如果沒有消耗輸入的轉換）或無限多的字符串有任何消費輸入的轉換）。

感應假設：假設所有k高達幷包括n，沒有NFA與k或更少的狀態接受字符串與長度不超過k更多和拒絕長度大於k更大字符串。

感應步驟：我們必須顯示沒有NFA與k+1或更少的狀態接受字符串與長度不超過k+1更多和拒絕長度大於k+1更大字符串。假設有這樣的NFA。考慮一下這個NFA的接受狀態。除了初始狀態以外，至少必須有一個，因爲NFA接受有限的多個字符串，而不僅僅是空字符串（請參閱k = 1的基本情況）。此外，NFA中必須有一些州可以接觸到其他一些接受州，因爲必須消耗一些投入來達到這些州。考慮一組通過消耗一個輸入符號可以達到其他接受狀態的狀態。考慮一個新的NFA，其他接受狀態被替換爲標記爲接受的這組新狀態。由此產生的NFA接受不超過k個狀態的所有長度不超過k的字符串（因爲我們從一組k + 1個狀態中刪除至少一個其他接受狀態）。這與歸納假設相矛盾，因此不存在不超過k + 1個狀態的NFA來接受所有長度不超過k + 1的字符串。

Answer 2

該聲明對於長度爲< k的情況屬實。

對於長度< = k考慮一個長度爲k的字符串w。它沿着某條路被接受。此路徑訪問k + 1個狀態。由於只有k個不同的州，至少其中一個被訪問兩次。所以路徑中有一個循環。該循環可以進行多次。因此可以接受無限多的字符串，特別是也可以是長度大於k的字符串。