雖然老師已經回答了，
但我真的不太懂…
P13-53頁例35題目：証明語言L={a^k b^k k >=1}不為有限狀態語言其中說明：假設一個FSA認知L
令M之狀態個數S=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個狀態嗎？
其實都是同一個問題，
真的不懂才會重複PO文
不好意思
彭彭留
2 則留言:
如果一開始 machine 的狀態總數改為 M (M>N), 此時取 (a^N)(b^N) 證不出來, 那就改取 (a^M)(b^M)來證, 最後可導出 a^(M-x)b^M 會被該 FSA accept, 和原先的意思一樣, 重點是不管總狀態數找多少, 你都可以利用找的那個數來導出矛盾
要注意的是你在一開始決定狀態總數是 x 後, x 就不可以再更改了, 此時可用 (a^x)(b^x) 證, 但不能在之後又拿一個比 x 更大的數 y, 宣稱 y 才是真正的狀態總數, 因為像這樣任意的更改, 就變成像是有無限個狀態了, 不算是finite state
感謝wynne的回答
可能是我太固執，
別想太多就好了…
張貼留言