第一題
96成大要將mealy model 化簡後的第2小題 求將S3 S6 分開的方法
是指說用最少字串丟入兩者後 會跑出不同結果的意思嗎?
答案是0000
如果照上面說法 "0100" 不是也可嗎? 就結果而言 最後也是有分開
所以答案不只一組解?
第二題
證L i={(a^k)(b^k)|k>=1} 證L is not a finite state machine
1.不存在FSA認知L
是代表L無法用FSM畫出來的意思嗎?
2.令N表M之state
Si0->Si1---->Sin
共有n+1個states ------> 所以存在兩個states相同
這句話我搞不懂
他是指因為令N表示M之state 所以必須想辦法把state壓在n以下 所以必有一個被走兩次的意思嗎?
那為何沒考慮到b^n呢? 壓在N以下應該a^n,b^n兩個都要考慮進去才對阿?
3.(a^N-X)(b^n)被M所accept 即為矛盾
why? 不走重複的states 但是只要走到 大圈圈包小圈圈 這個符號 不也就被accept了嗎?
為何(a^k)(b^k) 與 (a^N-X)(b^N)兩者皆存在 就是矛盾?
思緒挺亂的 不好意思 懇請解答
1 則留言:
1. 上課應該有提到, 答案並不止一組解
2. (1)不是不能用FSM畫出, 是無法被FSA認知, 就是所有L的字串都要走到accept state且所有不是L的字串都不能走到accept state, 要證明這樣的FSA造不出來
(2)存在二個state相同是根據鴿籠, 我想這個還好, 然後我們把第一段有重複的不走, 就少走了x個a, 至於第二段也會有重複, 我上課有提過, 有重複也照走, 然後只要有一種走法會產生矛盾就可以了, 不過去管第二段會重複幾個
(3)再重複一遍, 所謂的認知一定要所有不落在L的字串都reject才行, 我們現在有一種走法走到accept state, 但走的字串不在L中, 這個會與M認知L矛盾
上課也提過這一題會比較難理解, 主要的原因是無法給個例子, 因為這種Machine事實上並不存在, 加油, 若還有問題, 歡迎利用下課時間再來問我
張貼留言