8.1
{a^n b^n}{ww^R} 不是regular, 是context-free
{a^n b^n c^n}{ww} 不是context-free, 用pumping lemma證, 但可被turing machine所接受
9.1
所謂algorithm就是一個會停的turing machine
圖靈機: https://zh.wikipedia.org/wiki/%E5%9B%BE%E7%81%B5%E6%9C%BA
為一種數學邏輯機，可以看作等價於任何有限邏輯數學過程的終極強大邏輯機器。
現在電腦的組成就是一種圖靈機。
圖靈機是比pushdown automata更強的一種邏輯器,
它可以處理到REC Language以內的問題。
也就是說, REC Language以內的問題, 是電腦可以解的問題。(Fig 11.4,11.5)
沒有留言:
張貼留言