有限狀態機（FSM:finite-state machine ）或有限狀態機（FSA:finite-state automaton）、有限自動機或簡單的狀態機是計算的數學模型。它是一個抽象的機器，在任何給定的時間內都可以處於有限個狀態中的一個。FSM可以根據一些外部輸入從一個狀態更改為另一個狀態；從一個狀態更改為另一個狀態稱為轉換。FSM由其狀態列表、初始狀態和每個轉換的條件定義。有限狀態機有兩種類型——確定性有限狀態機和非確定性有限狀態機。確定性有限狀態機可以構造為任何非確定性狀態機。
現代社會的許多裝置都可以觀察到狀態機的行為，這些裝置根據一系列事件來執行預定的動作序列。簡單的例子是自動售貨機，當硬幣的正確組合存放時，自動售貨機分配產品；電梯，其停止順序由乘客要求的樓層決定；交通燈，當汽車等待時改變順序；組合鎖，需要按正確的順序輸入組合號。
有限狀態機的計算能力比其他一些計算模型（如圖靈機）要小，計算能力的區別意味著圖靈機可以完成但FSM不能完成的計算任務。這是因為FSM的內存受其狀態數的限制。FSMS是在更一般的自動機理論領域進行研究的。
緣起
一個可以用狀態機模擬的簡單機械裝置的例子是旋轉柵門。旋轉柵門用於控制地鐵和遊樂園遊樂設施的進出，它是一個在腰部高度有三個旋轉臂的門，一個在入口通道上。最初被鎖住，堵住入口，防止顧客通過。把硬幣或代幣放在旋轉柵門上的一個槽中，就能打開門把手，讓一個顧客可以通過。客戶通過後，手臂再次鎖定，直到插入另一枚硬幣。
作為狀態機，旋轉柵門有兩種可能的狀態：鎖定和解鎖。有兩種可能的輸入影響其狀態：將硬幣放入槽（硬幣）和推動臂（推動）。在鎖定狀態下，推動臂沒有任何作用；無論給多少次輸入推動，它都保持鎖定狀態。把硬幣放進去——也就是給機器一個硬幣輸入——將狀態從鎖定轉換為解鎖。在解鎖狀態下，放入額外的硬幣沒有效果；即，提供額外的硬幣輸入不會改變狀態。但是，客戶通過手臂推動，提供推動輸入，將狀態切換回鎖定狀態。
轉門狀態機可以用狀態轉換表表示，顯示每個可能的狀態、它們之間的轉換（基於給機器的輸入）和每個輸入產生的輸出：
轉門狀態機也可以用一個稱為狀態圖的有向圖來表示。每個狀態都由一個節點（圓）表示。邊（箭頭）顯示從一種狀態到另一種狀態的轉換。每個箭頭都標有觸發轉換的輸入。不引起狀態變化的輸入（如處於解鎖狀態的硬幣輸入）由返回原始狀態的圓形箭頭表示。從黑點進入鎖定節點的箭頭表示它是初始狀態。
概念和術語
狀態是對正在等待執行轉換的系統狀態的描述。轉換是在滿足條件或接收到事件時要執行的一組操作。例如，當使用音頻系統收聽收音機時（系統處於「收音機」狀態），接收到「下一個」刺激會導致移動到下一個電臺。當系統處於「cd」狀態時，「next」刺激會導致移動到下一個軌道。相同的刺激根據當前狀態觸發不同的動作。
在某些有限狀態機表示中，也可以將動作與狀態關聯：
進入動作：進入狀態時執行。退出操作：退出狀態時執行。表示
狀態圖是計算機科學和相關領域用來描述系統行為的一種圖。狀態圖要求所描述的系統由有限數量的狀態組成；有時確實如此，而有時這是一個合理的抽象。存在多種形式的狀態圖，它們略有不同，語義也有所不同。
狀態/事件表
使用了幾種狀態轉換表類型。最常見的表示形式如下：當前狀態（例如B）和輸入（例如Y）的組合顯示下一個狀態（例如C）。完整操作的信息沒有直接在表中描述，只能使用腳註添加。包含完整動作信息的FSM定義可以使用狀態表（另請參見虛擬有限狀態機）。
UML狀態機
統一建模語言有一個描述狀態機的符號。UML狀態機克服了傳統有限狀態機的局限性，同時保留了它們的主要優點。UML狀態機引入了層次嵌套狀態和正交區域的新概念，同時擴展了操作的概念。UML狀態機具有Mealy機器和Moore機器的特性。它們支持依賴於系統狀態和觸發事件的操作，如在Mealy機器中，以及與狀態而非轉換相關的進入和退出操作，如在Moore機器中。
SDL狀態機
規範和描述語言是ITU的一個標準，其中包括描述轉換中動作的圖形符號：
發送事件接收一個事件啟動計時器取消計時器啟動另一個並發狀態機決策SDL嵌入稱為「抽象數據類型」的基本數據類型、操作語言和執行語義，以便使有限狀態機可執行。
用法
除了在這裡介紹的系統建模中的應用之外，有限狀態機在許多不同的領域中都具有重要意義，包括電氣工程、語言學、計算機科學、哲學、生物學、數學和邏輯。有限狀態機是在自動機理論和計算理論中研究的一類自動機。在計算機科學中，有限狀態機廣泛應用於應用行為建模、硬體數字系統設計、軟體工程、編譯器、網絡協議以及計算和語言研究。
分類
有限狀態機可以細分為傳感器、接收器、分類器和序列器。
接受者（識別者）
接收器（也稱為識別器和序列檢測器）產生二進位輸出，指示是否接受接收的輸入。FSM的每個狀態要麼是「接受」，要麼是「不接受」。收到所有輸入後，如果當前狀態為接受狀態，則接受輸入；否則拒絕輸入。通常，輸入是一系列符號（字符）；不使用動作。
一組（可能是無限的）符號序列，又名。形式語言，如果有某個有限狀態機恰好接受該集合，則稱為常規語言。例如，偶數為零的二進位字符串集是一種常規語言，而長度為質數的所有字符串集不是。
機器也可以被描述為定義一種語言，該語言包含機器接受的每個字符串，但不包含被拒絕的字符串；該語言被機器「接受」。根據定義，FSM接受的語言是常規語言——如果有一些FSM接受，那麼語言就是常規語言。
確定給定的有限狀態接受者所接受的語言的問題是代數路徑問題本身的一個實例，它將最短路徑問題推廣到具有由（任意）半環元素加權的邊的圖上。
開始狀態也可以是接受狀態，在這種情況下，自動機接受空字符串。
分類器
分類器是有限狀態機的一種推廣，它類似於接受者，在終止時生成單個輸出，但有兩個以上的終止狀態。
換能器
傳感器根據給定的輸入或使用動作的狀態生成輸出。它們用於控制應用和計算語言學領域。
在控制應用程式中，可區分兩種類型：
摩爾機
FSM僅使用入口操作，即輸出僅取決於狀態。摩爾模型的優點是簡化了行為。考慮一個電梯門。狀態機識別兩個命令：「命令打開」和「命令關閉」，觸發狀態更改。進入動作（E:）在「打開」狀態下啟動電機打開車門，在「關閉」狀態下啟動電機在另一方向關閉門。狀態「打開」和「關閉」在完全打開或關閉時停止電機。它們向外部世界（例如，向其他電梯）發出「門是開的」或「門是關的」的信號。
梅利機
FSM還使用輸入動作，即輸出取決於輸入和狀態。使用有限的FSM通常會導致狀態數量的減少。示例顯示了一個實施與摩爾示例中相同行為的簡單FSM（該行為取決於實施的FSM執行模型，並且將起作用，例如，對於虛擬FSM，但對於事件驅動的FSM不起作用）。有兩個輸入動作（i:）：「如果命令關閉到達，啟動電機關閉車門」和「如果命令打開到達，啟動電機向另一個方向打開車門」。未顯示「打開」和「關閉」中間狀態。
序列器
序列器或發生器是具有單個字母輸入字母表的接受器和傳感器類型的一個子類。它們只產生一個序列，可以看作是接受器或傳感器輸出的輸出序列。
決定論
另一個區別是確定性（dfa）和非確定性（nfa，gnfa）自動機。在確定性自動機中，每個狀態對於每個可能的輸入只有一個轉換。在非確定性自動機中，輸入可以導致給定狀態的一個、多個或沒有轉換。Powerset構造算法可以將任何非確定性自動機轉換為具有相同功能的（通常更複雜）確定性自動機。
只有一種狀態的有限狀態機稱為「組合FSM」。它只允許在轉換到狀態時執行操作。這個概念在需要許多有限狀態機一起工作的情況下是有用的，並且當把一個純粹的組合部分看作一種適合設計工具的FSM形式時也是很方便的。
替代語義學
還有其他一些語義可以用來表示狀態機。例如，有一些用於為嵌入式控制器建模和設計邏輯的工具。它們將分層狀態機（通常具有多個當前狀態）、流程圖和真值表組合成一種語言，從而形成不同的形式主義和語義集。這些圖，如Harel的原始狀態機[12]支持層次嵌套狀態、正交區域、狀態操作和轉換操作。
優化
優化一個FSM意味著找到一個具有執行相同功能的最小狀態數的機器。最快的已知算法是Hopcroft最小化算法其他技術包括使用蘊涵表或摩爾約簡過程。此外，非循環FSA可以在線性時間內最小化。
實施
硬體應用
在數字電路中，可以使用可編程邏輯器件、可編程邏輯控制器、邏輯門和觸發器或繼電器來構建FSM。更具體地說，硬體實現需要一個寄存器來存儲狀態變量，一個確定狀態轉換的組合邏輯塊，以及第二個確定FSM輸出的組合邏輯塊。典型的硬體實現之一是理查茲控制器。
在Medvedev機器中，輸出直接連接到狀態觸發器，以最小化觸發器和輸出之間的時間延遲。
對於低功耗狀態機，可以通過狀態編碼進行優化，以最小化功耗。
軟體應用程式
以下概念通常用於使用有限狀態機構建軟體應用程式：
基於自動機的程序設計事件驅動有限狀態機虛擬有限狀態機狀態設計模式有限狀態機和編譯器
有限自動機常用於程式語言編譯器的前端。這樣的前端可能包含幾個有限狀態機，它們實現詞彙分析器和語法分析器。從一系列字符開始，詞彙分析器構建一系列語言標記（如保留字、文本和標識符），解析器從中構建語法樹。詞彙分析器和解析器處理程式語言語法的常規部分和上下文無關部分。