在黃老師及課本都有的一題 P13-53頁例35
題目：証明語言L={a^k b^k k >=1}不為有限狀態語言
其中說明：
假設一個FSA認知L
令M之狀態個數S=N
Q1.為何如此令呢？不能超過N個狀態嗎？
其後又說明有N+1個狀態，
所以有兩個狀態相同
所以a^(N-x) b^N 被認知，得証
請各位大大幫忙小弟了解這個問題。
謝謝
4 則留言:
令為N只是為了方便證明而已
就像我們的數學歸納法可以令k=n或k=n-1一樣
就只是為了方便而已...
若你要令S=N+1
那後面的N+1就要改成N+2
以此類推...
至於有N+1個狀態所以有兩個狀態必相同是依據了"鴿籠原理"
(存在N個籠子，若有N+1隻鴿子欲飛進籠子，必會有兩隻鴿子會在同一個籠子裡...)
所以就代表了會有兩個states是相同的...
(ex. N=４：
S1→S2→"S3"→"S4"→S5→S6→S7→S8的結果可能會跟：
S1→S2→S5→S6→S7→S8
的結果是一樣的)
最後的a^(N-x) b^N是指原本可能為：aaa...aaabbb...bbb (n個a + n個b)
但也會另外存在aa...aabbb...bbb (少了x個a，變成：a^(N-x) b^N)
一樣可以到達"accept state"
剛好呼應了上面鴿籠原理的結果
所以因為有兩個不同的"語言"可以達到"accept state"
故得證：不存在FSL認知該L
我數學不好...
會回答也只是因為剛好今天補課的時候有上到而已... QQ
所以如果有回答不對或不恰當的地方歡迎指教及修正!!
一個Finite state machine被決定後, 它的狀態數即固定, 只是令它的狀態數為N, 如此而已, 其他的 法克 寫得很清楚了
其上的証明，
是說明若狀態數是N種
可証明它無法認知a^N b^N
因為有兩個狀態相同，
所以有a^(N-x) b^N 及a^N b^N
均可能被認知。
Q1.可否用M個狀態認知a^N b^N ？其中M>N
Q2.再轉一個問題好了，
如果有一機器可以認知a^N b^N
其狀態數一定是N個狀態嗎？
不能是M個狀態嗎？
張貼留言