2009-10-31

[離散數學課本]

第十三章。

1、13-39例25:
    請問此題有其他解法嗎?還是說為了討論i不等於j所以非得拆開討論..

2、13-43範例2之(b):
    請問為何是 context-sensitive,不是 context-free 的原因是?

3、13-46範例6:
    grammar這種東西應該很難有標準答案吧。不過我想問的是,如果題目沒限制,
    那麼有幾條production rules應該都可以吧?比如這題我是寫..
    P = { S→Ab, A→aAb, A→空, B→Aa, B→空 }

4、13-61範例6:
    S0跟S4的0.0是不是應該是接到S1跟S4?

5、13-71範例5之(a):
    最後F接到C的地方感覺是錯的..題目不是規定須以abc為字首,雖然C有b,c 的loop,
    不過C若走a不就錯了?還是說FSA定義我搞錯,應該是要滿足L的所有規定吧..

以上,請多指教。

1 則留言:

線代離散助教(wynne) 提到...

1. 13-39例25: 就像你說的 grammar 不會唯一, 分 case 討論是為了方便描述, 譬如我們如果想把此題的 FSA 畫出來, 大概也是會先建構出某個 a 比 b 多的 state, 和另一個 b 比 a 多的 state, 再分別去想後面要怎麼畫, 類似是這樣

2. p13-43範例2(b): context-free 描述的只能是從 1 個 nonterminal symbol 去推到其他的字串, 不能訂有像是 "AB→..." 這種由 2 個 nonterminal 推出去的東西出現

3. 13-46範例6: 你的版本不太符合題目的要求, 像 B 其實沒用到, 因為到不了, 而且如果訂 S→Ab, 那右邊就已經走到底不能再加東西了, 也就是說右邊就永遠不會生出 a

4. 13-61範例6: 這題書上的那個圖只要改一個地方, 就是上面少了一個由 S2→S0 的 1,0

5. 13-71範例5(a): 這題也有勘誤過了, 你可以去勘誤的連結那邊看一下改過的版本