自動機理論

出自維基百科,自由嘅百科全書
Jump to navigation Jump to search

自動機理論automata theory)研究抽象機械,以及唔同種類嘅抽象機械喺解難能力上有乜唔同。自動機理論最基本嘅諗頭係抽象機械(abstract machine),一部抽象機械內部有一啲函數會攞一啲輸入,按輸入計出一個輸出,例如係以下呢個極簡單嘅抽象機械[1]

DFAexample.svg

上圖呢部機械會攞一串符號做輸入,再話俾用家知,串符號入面 0 嘅數量係咪雙數:部機開始於 S1 狀態;當部機讀到一個 0 嗰陣,會進入 S2 狀態,而當佢再讀到個 0 嗰時,會返去 S1 狀態;如果佢讀到嘅係 1 或者第啲符號嗰時,部機唔會改變狀態;喺部機讀完嗮串符號之後,如果串符號入面 0 嘅數量係雙數,佢會處於 S1 狀態,否則佢就會處於 S2 狀態。呢部機械可以用多種嘅物理機制實現,係一部抽象機械。自動機理論會想像同研究種種抽象機械嘅特性以及佢哋喺解難能力上有乜差異,而呢啲研究對電腦嘅設計同改良好有幫助[1]

參考[編輯]

  1. 1.0 1.1 John E. Hopcroft, Rajeev Motwani, Jeffrey D. Ullman (2000). Introduction to Automata Theory, Languages, and Computation (2nd Edition). Pearson Education.