Formal Language 7.3 自讀

因為11/10期中考周沒去上課, 在此自己讀, 補起一些進度

7.1 介紹什麼是pda (pushdown automata)
它是導入一個Stack來儲存automata的資訊
使得automata本來是infinite的(無限多個), 變成finite(有限個)
進而可以用來表示context-free的語言
(原本的dfa和nfa都只能表示regular的語言, context-free比regular範圍更廣)

7.2 說明npda (non-deterministic pushdown automata)的建構和性質

理論 Thm7.1: 所有context-free的語言, 都可以被npda所接受

這節的題目, 主要是給你一個Grammar, 要你建構出一個npda
答案都只有用transition states表示 (但我個人習慣一定要畫圖, 才比較好思考)

Grammar --> Language --> 畫圖 --> 寫出transition states

如果遇到不能輕易看出language結構的Grammar, 會很難下手畫圖
就要試著將它轉成Greibath Normal Form, 這樣就可以跳過畫圖的步驟, 輕鬆寫出transition state

Grammar --> Greibath Nomal Form --> 寫出transition states

我不確定其他的Normal Form可不可以,
不過像是Chomsky Normal Form我想應該ok, 因為它比Greibath Normal Form更簡單

忘記這兩個Normal Form的話, 請複習一下6.2

可以參考這個網站, 裡面有提到這些Normal Form的設計目的

文法結構一旦改寫成 Chomsky Normal Form ， Parse Tree 就是一棵二元樹，得以設計高效率的資料結構與演算法。

7.3 說明在context-free L裡, deterministic的定義為何?
(翻譯: 什麼能算是dpda(deterministic pushdown automata)?什麼是npda?)

根據Def. 7.3: dpda的條件有兩個
(1)一個狀況(一種(q,a,b)的transition)只能有一條路可以選擇
(2)結束點( (q,空字元,b)的transition set 非空 )的結束字元一個state只有一種, 後面不會拖尾