有限狀態機
有限狀態機(FSM)是一種數學計算模型，用於表示有限個狀態以及在這些狀態之間的轉移和動作等行爲。
在FSM中，包含一組狀態集、一箇起始狀態、一組輸入符號集，以及一箇映射輸入符號和當前狀態到下一狀態的轉換函數。當輸入符號串時，模型隨即進入起始狀態，它會改變到新的狀態，依賴於轉換函數。FSM可以用狀態轉換圖來描述，圖中的節點表示FSM中的一箇狀態，有向加權邊表示輸入字符時狀態的變化。
FSM可以分爲兩大類，如果輸出只和狀態有關而與輸入無關，則稱爲Moore狀態機；如果輸出不僅和狀態有關而且和輸入有關係，則稱爲Mealy狀態機。