2016/11/17 Formal Language

今天的課程內容十分重要
- - -

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)

Machine	Language
finite state automata(nfa)	Regular
pushdown automata(npda)	Context-Free (CF)
turing machine	Recursively enumerable (RE)

• 何謂deterministic?

         指所有alphabet可能路徑, 最多都只有一條
         例如 alphabet = {a,b}
         每個state最多只會有一條a, 一條b

     

• 何謂halt?

        在TM中, halt states 指的是到達了一個transition state沒有定義的state, 那麼就會終止了