Ⅰ 有限狀態自動機類型
有限狀態自動機是一種理論模型，用於處理輸入和產生輸出。它主要有兩種類型：接收器和轉換器。接收器的作用是判斷輸入是否被接受，而轉換器，如Moore機和Mealy機，前者在每個狀態下定義輸出動作，後者則在每個狀態轉移中附帶輸出動作。
區分這兩種機器的是它們的確定性：確定有限狀態自動機（DFA）對於每個輸入僅有一個確定的狀態轉移，而非確定有限狀態自動機（NFA）則允許每個輸入有多個可能的轉移。NFA由五個元素組成：有限狀態集合Q，輸入字母表Σ，轉移函數δ，初始狀態q0和終結狀態集合F，它基於當前狀態、輸入和轉移函數決定後續狀態。當輸入結束後，如果機器停留在F中任一狀態，則表示接受該輸入，否則拒絕。
盡管NFA在理論上可能顯得復雜，但它在實際應用中十分廣泛，如數字電路設計、詞法分析和文本編輯器程序等。自動機識別的語言L(M)是由機器接受的所有字元串組成的集合，這是衡量其功能和性能的關鍵指標。
有限狀態自動機（FSM "finite state machine" 或者FSA "finite state automaton" ）是為研究有限內存的計算過程和某些語言類而抽象出的一種計算模型。有限狀態自動機擁有有限數量的狀態，每個狀態可以遷移到零個或多個狀態，輸入字串決定執行哪個狀態的遷移。有限狀態自動機可以表示為一個有向圖。有限狀態自動機是自動機理論的研究對象。