有限狀態機

有限狀態機（粵拼：jau5 haan6 zong6 taai3 gei1），又叫有限狀態自動機，係種運算模型。一部基本嘅有限狀態機會有呢啲部份：

• 若干（${\displaystyle n}$）個可能狀態，其中一個係部機開頭嗰陣嘅狀態（睇初始化）；
• 喺任何一個時間點 ${\displaystyle t}$，部有限狀態機會處於呢 ${\displaystyle n}$ 個可能狀態當中嘅其中一個；而且
• 啲狀態係離散嘅，部機唔能夠同時處於多過一個狀態；
• 狀態可以因為外界嘅輸入而改變，而一部有限狀態機由一個狀態去另一個嘅過程就係一次轉換^[1]。

交通燈有三個可能狀態－紅燈、黃燈同綠燈。

有限狀態機唔一定係決定嘅，如果話一部有限狀態機唔係決定，即係話部機帶有隨機，例：想像一部有限狀態機，有兩個可能狀態 ${\displaystyle {\text{S}}_{1}}$ 同 ${\displaystyle {\text{S}}_{2}}$，當中 ${\displaystyle {\text{S}}_{1}}$ 係開頭嗰陣嘅狀態；設計者可以將部機設計成「每當探測到光，就由 ${\displaystyle {\text{S}}_{1}}$ 轉換去 ${\displaystyle {\text{S}}_{2}}$」（決定），但又可以將部機設計成「每當探測到光，就有 50% 咁高嘅機會率由 ${\displaystyle {\text{S}}_{1}}$ 轉換去 ${\displaystyle {\text{S}}_{2}}$」（帶有隨機，所以唔係決定）^[2]。

好多廿一世紀初常見嘅機械都可以概念化想像成有限狀態機，例子有交通燈（紅燈、綠燈同黃燈三個狀態）^[3]同自動販賣機（一旦有客人入錢，就由「企喺度唔郁」狀態轉換成「將客人要嘅嘢放出嚟」狀態，放完變返「企喺度唔郁」）... 呀噉^[4][5]。除此之外，有限狀態機嘅技術喺廿一世紀初嘅電子遊戲 AI 領域上亦都成日用－遊戲製作師可以（例如）將遊戲入面嘅敵人角色設計成有限狀態機，有「企喺度唔郁」同埋（一旦同玩家角色之間嘅距離細過特定數值 ${\displaystyle n}$）「郁手攻擊玩家角色」等嘅狀態^[6][7]。

定義

幾部並排嘅閘機；閘機係一種簡單嘅有限狀態機，得兩個可能狀態－鎖咗同埋（因為有人入咗錢）開咗。

睇埋：運算模型、運算理論同相互遞歸

有限狀態機喺數學上定義係具有以下部份嘅五元組^{[註 1]} ${\displaystyle (\Sigma ,S,s_{0},\delta ,F)}$，當中^[2][8]：

• ${\displaystyle \Sigma }$ 係輸入（input）；
• ${\displaystyle S}$ 係 ${\displaystyle n}$ 個可能狀態嘅集合，${\displaystyle \{s_{0},s_{1},s_{2}...s_{n-1}\}}$，當中 ${\displaystyle n}$ 係一個有限數值，而且 ${\displaystyle n>0}$；
• ${\displaystyle s_{0}}$ 係部機嘅初始狀態（initial state），即係部機喺啱啱開機嗰陣嘅狀態，而 ${\displaystyle s_{0}\in S}$ ^{[註 2]}；
• ${\displaystyle \delta }$ 係狀態轉換函數（state-transition function），
  • ${\displaystyle \delta }$ 會指定「如果現時狀態係噉而輸入係噉，新狀態會係噉」嘅資訊：${\displaystyle \delta :S\times \Sigma \rightarrow S}$。
  • 而如果部機係有隨機嘅，${\displaystyle \delta }$ 會指定嘅係「如果現時狀態係噉而輸入係噉，進入每個新狀態嘅機會率會係噉」噉嘅資訊：${\displaystyle \delta :S\times \Sigma \rightarrow {\mathcal {P}}(S)}$ ^{[註 3]}。
  • ${\displaystyle \delta }$ 可以係一個局部函數（partial function），意思即係話 ${\displaystyle \delta }$ 唔使實要指定嗮每對可能「現時狀態」同「輸入」配對下嘅「新狀態」。
• ${\displaystyle F}$ 係部機嘅最終狀態（final state），部機進入咗呢個狀態就唔會再改變狀態；${\displaystyle F\subset S}$。${\displaystyle F}$ 可以係一個空集，意思即係話一部有限狀態機可以係冇最終狀態嘅。

有關呢啲數學概念嘅詳情，可以睇吓集合論相關嘅嘢。喺運算能力上，有限狀態機渣過圖靈機，即係話有啲運算問題係圖靈機解得到，但有限狀態機解唔到嘅^[9]。不過有限狀態機喺工程學上依然相當有用，可以用嚟將好多種機械概念化。

簡例

好似閘機就係一個簡單嘅例子：閘機係一種喺車站同遊樂園入口等嘅地方成日見到嘅機械，通常到大人嘅腰咁高，用途係要確保啲人要俾錢先至可以通過；一部基本嘅閘機會有^[10]

• 兩個狀態（${\displaystyle n=2}$）－鎖咗（${\displaystyle s_{0}}$）同開咗，過得（${\displaystyle s_{1}}$），當中前者係初始狀態；
• 喺鎖咗嘅狀態下，部閘機嘅柄喺鎖死咗郁唔到嘅，但一旦有人俾咗「入銀仔」嘅輸入（${\displaystyle {\text{coin}}}$），部閘機會轉換成開咗嘅狀態（${\displaystyle s_{0}\times {\text{coin}}\rightarrow s_{1}}$）；
• 喺開咗嘅狀態下，部閘機嘅柄轉得郁，而如果啲柄俾人㧬ung2到轉咗一個圈（${\displaystyle {\text{push}}}$），部閘機會返去鎖咗嘅狀態（${\displaystyle s_{1}\times {\text{push}}\rightarrow s_{0}}$）；
• 喺鎖咗嘅狀態下，部閘機嘅柄俾人點㧬都唔會郁，狀態會唔變（${\displaystyle s_{0}\times {\text{push}}\rightarrow s_{0}}$）；
• 喺開咗嘅狀態下，就算有人入銀仔，狀態依然會唔變（${\displaystyle s_{1}\times {\text{coin}}\rightarrow s_{1}}$）；

如果將上述講嘅嘢畫成理想化嘅圖解（狀態圖）嘅話會係噉^[10][11]：

狀態圖

呢幅狀態圖描述一道門。

内文：狀態圖

喺電腦科學同相關領域上，研究者成日都會用有限狀態機嘅概念嚟做分析，而做分析嘅第一步通常係將部機以某啲形式表達出嚟。一般嚟講，表達有限狀態機嘅最直接方法係用狀態圖。一幅狀態圖會有以下嘅組成部份^[12][13]：

• 若干個節點（node），每個節點代表一個狀態，例如附圖嗰幅狀態圖描述嘅係一道門，道門有兩個狀態，開咗同閂埋咗，每個狀態喺幅圖入面係一個灰色嘅圓形；
• 若干個箭咀，每條箭咀表示一個可能嘅轉換，而且每條箭咀會掕住一啲字，描述轉換條件（transition condition），例如附圖，要由閂埋咗轉換去開咗，一個用家要做開門（open）嘅動作（轉換條件）；
• 指明邊一個狀態係初始狀態，例如附圖當中嘅「entry action」指住閂埋咗嘅狀態，表示閂埋咗嘅狀態係道門嘅初始狀態。

狀態圖唔一定會指明一部有限狀態機嘅狀態轉換函數，不過能夠有效噉將有限狀態機以視覺化嘅方式呈現出嚟，對於有限狀態機相關嘅研究嚟講好使好用^[13]。

分類

睇埋：自動機理論

接受機

内文：接受機

接受機（acceptor）做嘅工作係產生一個二元嘅輸出（1 定 0），用嚟表示個輸入係咪俾部機接受（所以叫接受機），數學啲噉講，一部有限狀態機嘅狀態當中有一部份會係所謂嘅接受狀態（${\displaystyle A}$），${\displaystyle A\subset S}$，而部機嘅初始狀態可以係一個接受狀態，接受機輸入通常會係一串符號，可以用嚟運算一串符號係咪設計想要嘅。舉個例說明，想像以下嘅有限狀態機，部機會攞一串字做輸入，將串字逐個逐個睇，如果串字係英文字詞 nice，噉部機最後會達到成功嘅狀態，而呢個狀態係部機唯一一個接受狀態，如果串字唔夾，噉部機會進入出錯嘅狀態^[14][15]：

接受機一個常見用途係攞嚟處理語言，不過接受機亦都可以用嚟處理數字方面嘅運算，例如以下呢部噉嘅接受機可以用嚟睇一個數係咪 3 嘅倍數：想像串輸入係 1001 －呢串嘢係一個用二進制寫嘅數字，等同於十進制當中嘅 9，部機會將個數字嘅位由細嘅做起始、逐個逐個睇，1001 呢串嘢如果入落去以下嘅接受機嗰度，會令部機經過以下嘅連串狀態：

${\displaystyle S_{0}\rightarrow S_{1}\rightarrow S_{2}\rightarrow S_{1}\rightarrow S_{0}}$

－最後處於 ${\displaystyle S_{0}}$ 呢個接受狀態（呢個接受狀態表示個數係 3 嘅倍數）^[13]。

傳感機

内文：有限狀態傳感機

有限狀態傳感機（finite-state transducer，FST）會好似圖靈機噉有一條輸入帶同一條輸出帶：一般嘅有限狀態機淨係曉按輸入改變自己嘅狀態，頂櫳做到以「自己嘅狀態」直接攞嚟做輸出；而相比之下，一部有限狀態傳感機會按輸入改變自己嘅狀態，而輸出會係「部機嘅狀態」嘅函數（輸出函數，${\displaystyle O}$），即係話輸出取決於「部機嘅狀態」。而用數學行話嚟講嘅話，有限狀態傳感機可以話係有限狀態機嘅一種廣義化－有限狀態機可以當係「${\displaystyle O}$ 係一個恆等函數」嘅有限狀態傳感機^[16][17]。

好似係下圖呢部機噉，狀態（啲圓形）之間可以轉換（箭咀），而一個箭咀掕住嘅符號係指「部機喺經歷呢個轉換嗰陣會出嘅符號」，例如由 code 去 slash 再去 block 嘅過程會出 /*。

有限狀態傳感機仲可以再細分做兩種^[18]：

• 摩亞機，指輸出完全由部機嘅狀態話事，同埋
• 美利機，指輸出同時由部機嘅狀態以及輸入話事。

有限狀態傳感機喺自然語言處理（NLP）上成日會用到^[19]。自然語言處理泛指教人工智能處理自然語言嘅工作^[20]，好似係機械翻譯噉，機翻研究點樣用電腦軟件嚟幫手翻譯一啲用自然語言寫嘅文字，而一個程式做翻譯嗰陣，個程式要識睇嗮成句句子，甚至乎係成段嘢，了解當中每個字嘅意思先決定俾乜嘢輸出^[21]。可以睇埋遞迴神經網絡嘅嘢。

按決定性嚟分

内文：決定型有限狀態機同非決定型有限狀態機

有限狀態機嘅一個重要分類準則係「係咪帶有隨機」：喺數學上，隨機大致上可以定義做「本質上唔能夠完美噉預測嘅嘢」，現實例子有掟銀仔同擲骰仔等嘅現象，而概率論等嘅數學理論有詳細探討隨機相關嘅問題^[22]；決定型有限狀態機係指完全決定嘅有限狀態機，柞 ${\displaystyle \delta }$ 會指明要去邊一個狀態，而非決定型有限狀態機就啱啱相反，唔完全決定，一部非決定型有限狀態機嘅 ${\displaystyle \delta }$ 會掕住機會率（反映一件事有幾大機會發生）數值，講明（例如）「如果喺呢個呢個狀態（${\displaystyle S}$）接收到 ${\displaystyle \Sigma }$ 噉嘅輸入，有 ${\displaystyle {\text{Pr}}_{1}}$ 咁大機會去 ${\displaystyle S_{1}}$、${\displaystyle {\text{Pr}}_{2}}$ 咁大機會去 ${\displaystyle S_{2}}$...」等嘅資訊^[23][24]。

例如以下呢部有限狀態機就係非決定型嘅，由狀態 ${\displaystyle {\text{p}}}$ 接收到輸入「1」可以去 ${\displaystyle {\text{p}}}$ 或者去 ${\displaystyle {\text{q}}}$。

工程分析

睇埋：機械同系統

除咗閘機之外，仲有好多現代社會常用嘅機械同系統都可以想像成有限狀態機：

交通燈

内文：交通燈

交通燈係另一種成日俾人攞嚟做有限狀態機嘅例子嘅機械^[3]。想像以下嘅簡單例子：家陣有個十字路口，（上當係北）一條打橫嘅馬路（${\displaystyle L_{A}}$）同一條打戙嘅馬路（${\displaystyle L_{B}}$）喺呢個十字路口相交（可以睇吓下圖），而啲車淨係可以去對面條路－由北面嚟嘅車淨係可以向南面駛、由西面嚟嘅車淨係可以向東面駛... 如此類推；而家有個工程師，佢需要設計點樣擺低一啲交通燈嚟控制呢個十字路口嘅車流，呢兩個十字路口嘅交通燈可以想像成有四個狀態嘅有限狀態機（${\displaystyle n=4}$），而喺最簡單嘅情況下，呢部有限狀態機會每隔一段特定長度嘅時間就跳去下一個狀態（「${\displaystyle t{\text{ passes}}}$」表示「${\displaystyle t}$ 咁耐嘅時間過咗」）^[25]：

• ${\displaystyle S_{0}}$，${\displaystyle L_{A}}$ 綠燈、${\displaystyle L_{B}}$ 紅燈，呢個係初始狀態（${\displaystyle s_{0}}$）；${\displaystyle S_{0}\times t_{0}{\text{ passes}}\rightarrow S_{1}}$
• ${\displaystyle S_{1}}$，${\displaystyle L_{A}}$ 黃燈、${\displaystyle L_{B}}$ 紅燈；${\displaystyle S_{1}\times t_{1}{\text{ passes}}\rightarrow S_{2}}$
• ${\displaystyle S_{2}}$，${\displaystyle L_{A}}$ 紅燈、${\displaystyle L_{B}}$ 綠燈；${\displaystyle S_{2}\times t_{2}{\text{ passes}}\rightarrow S_{3}}$
• ${\displaystyle S_{3}}$，${\displaystyle L_{A}}$ 紅燈、${\displaystyle L_{B}}$ 黃燈；${\displaystyle S_{3}\times t_{3}{\text{ passes}}\rightarrow S_{0}}$
• 呢部有限狀態機並冇最終狀態，${\displaystyle F=\varnothing }$ ^{[註 4]}。

${\displaystyle L_{B}}$

${\displaystyle L_{A}}$

想像中嘅十字路口由上空望嘅圖解

土木工程同城市規劃等領域嘅工作者會花好多時間精神諗交通燈系統嘅設計：一個城市嘅順利運作相當有賴於車流嘅控制；車流控制得唔好會搞到啲路出現塞車嘅情況，塞車會阻礙啲人返工或者運送貨品，而呢啲活動受阻會搞到個城市嘅生產變慢，對經濟有負面嘅影響；因為噉，相關嘅工程學領域抌好多資源研究點樣改善交通燈系統嘅設計，呢啲研究往往會將交通燈系統想像成有限狀態機，然後再用電腦模擬「假設啲司機按正常方法揸車（見到紅燈就停車、係綠燈就踩油...）嘅話，呢個噉嘅路口（路口有好多唔同種類）同呢個噉嘅交通燈系統結合埋會產生點樣嘅車流」，並且靠噉嚟比較唔同交通燈系統嘅表現^{[註 5][26][27]}。

自駕車

一架自駕車行嘅片

内文：自駕車

自駕車係指唔使人特登操作都曉行去目的地嘅汽車，通常會用到人工智能（AI）技術。而家假想有架自駕車，佢內置咗適當嘅感應器同相關嘅人工智能技術（可以睇吓電腦視覺），令個人工智能識得正確噉判斷自己身處喺乜嘢情況入面－可能嘅情況包括咗「身處十字路口」、「身處高速公路」同埋「身處停車場」呀噉^[28]；而個人工智能可以設成一部有限狀態機，每個呢啲情況做一個狀態，跟住再編寫類似以下噉嘅程式，以下呢個程式教架車判斷周圍每一架車喺條路嘅邊條線^[29]：

if (d > 0 && d < 4) // d 表示架車嘅打橫坐標，單位係米，當中 0 表示條路左面嗰條邊嘅坐標。
  {
    car_lane = 0; // 如果有架車嘅 d 係 0 - 4 米，噉佢係身處喺左邊條線（car_lane = 0）
  } else if (d > 4 && d < 8) {
    car_lane = 1; // ... 噉佢係身處喺中間條線（car_lane = 1）
  } else if (d > 8 && d < 12) {
    car_lane = 2; // ... 噉佢係身處喺右邊條線（car_lane = 2）
  }
if (car_lane < 0) // 喺條路外面嘅車可以忽略。
{
    continue;
}

得到咗周圍嘅車「喺邊條線」同「喺乜嘢位置」以及條路係點樣（例：前面係咪要掟彎）等嘅資訊之後，架車可以按簡單嘅法則決定自己嘅狀態，例如係：

if (car_ahead) // 如果處於「前面有車」呢個狀態。
  {
    cout << "Car Ahead!!!\n\n\n\n\n\n" // 顯示「前面有車！！」嘅字
       << endl;
    if (!car_left && lane > 0) // 如果左邊有線而且冇車...
    {
      lane--; // ... 就轉去左邊線。
    }
    else if (!car_right && lane != 2) // / 如果右邊有線而且冇車...
    {
      lane++; // ... 就轉去右邊線。
    }
    else // 如果兩邊都有車...
    {
      speed_diff -= max_acl; // ... 就減慢車速。
    }
  }
  else // 如果唔係處於「前面有車」呢個狀態。
  {
    if (lane != 1) // 如果自己唔喺中間線...
    {
      if ((lane == 0 && !car_right) || (lane == 2 && !car_left)) // 又如果中間線冇車...
      {
        lane = 1; // ... 就轉去中間線。
      }
    }
    if (ref_vel < max_vel) 
    {
      speed_diff += max_acl;
    }
  }

直去緊、要掟彎同埋見到紅燈等嘅狀態之間可以按類似嘅原理想像^[29]。

電子遊戲應用

睇埋：電子遊戲 AI

喺電子遊戲人工智能上，有限狀態機可以用嚟教遊戲嘅 NPC 做決策：電子遊戲好多時會涉及由電腦控制、同玩家進行對局嘅角色，遊戲開發者為咗想玩家得到樂趣，通常會想呢啲由電腦控制嘅角色有返咁上下聰明，能夠為玩家提供一定嘅挑戰，即係話佢哋會想 NPC 展現一定程度嘅智能，而有智能嘅物體係理應要曉做決策嘅^[6]。

直至廿一世紀初為止，有限狀態機依然係其中一種最多人用嘅遊戲 AI 做法例如想像一個寫嚟教電腦玩射擊遊戲嘅 AI，個 AI 係一部有限狀態機，有防守、進攻同去搵彈藥等多個可能狀態，佢內置嘅 AI 演算法就要教佢幾時進入邊個狀態（例：if 自己淨低嘅生命值低過 50%，then 進入防守狀態－教佢喺自己血低嗰陣要防守）。呢類決策演算法會攞同遊戲輸贏相關嘅資訊（自己同對手血量等等），並且計出要進入邊個狀態（採取邊個策略）。有限狀態機同搵路呢兩個概念係遊戲 AI 嘅基礎^[30][31]。

一個以有限狀態機形式存在嘅遊戲 AI 望落會有類似噉嘅碼^[6]：

void Update(){ // 呢段碼教一個 AI 玩揸戰機。
  switch(state){ // 視乎 state（狀態）係乜，做...
    case State.PURSUIT: // 如果狀態係 pursuit（追擊）嘅話，做...
      CheckForDanger(); // 一個睇吓周圍有冇危險嘅子程序
      Chase(target, true); // 追目標；呢個子程序當中會有演算法，決定幾時要將 state 呢個變數改變並且離開個子程序。
      break;

    case State.DARWINISM: // 如果狀態係 Darwinism 嘅話，做...
      var angle = GetDeltaAngle(target); // ... 同一道理
      SteerClear(angle);
      if(!IsOnCollisionCourse) state = pausedState;
      break;

    case State.FOLLOW: // ...
      CheckForDanger();
      Chase(squadron.leader);
      EvaluateSquadron();
      break;

    case State.PATROL: // ...
      CheckForDanger();
      FlyTo(route.goingTo);
      PatrolManagement(20);
      break;
  }

void Chase(target, true){ // Chase 呢個子程序
    ... // 做 chase 狀態要做嘅行動。
    if (.....) // 如果某啲條件達到...
       break; // 離開子程序，令個程式返到去揀狀態嘅點。
  }

同圖靈機對比

睇埋：圖靈機

理論上，有限狀態機嘅運算能力可以話係渣過圖靈機。圖靈機係另一種運算理論上成日討論嘅運算模型。用言語講嘅話，一部圖靈機嘅運作方式如下：一部圖靈機會讀取一條分做若干個格嘅帶，條帶每個格裏面都會有個符號（可以係 1 同 0 等多個款）；喺每一個時間點，部圖靈機個讀取器都會位於條帶其中一格，而部機就會做以下三個基本作業當中任何一個^[32][33]：

1. 讀取讀取器下嗰格係乜符號；
2. 編輯嗰格－寫一個新嘅符號落去或者刪除咗嗰格佢；
3. 將條帶向左或者向右移一格，等個讀取器可以讀取打前嗰個格隔離嘅一個格。

圖靈機嘅想像圖如下：

圖靈機又可以想像成具有以下部份嘅物體^[33]：

• ${\displaystyle S}$ 係 ${\displaystyle n}$ 個可能狀態，${\displaystyle \{s_{0},s_{1},s_{2}...s_{n-1}\}}$，當中 ${\displaystyle n}$ 係一個有限數值，而且 ${\displaystyle n>0}$；
• ${\displaystyle s_{0}}$ 係部機嘅初始狀態，即係部機喺啱啱開機嗰陣嘅狀態，而 ${\displaystyle s_{0}\in S}$；
• ${\displaystyle \Sigma }$ 係輸入（input）；
• ${\displaystyle \Gamma }$ 指容許嘅輸入符號嘅集合，而呢個集合係有限嘅；（有限狀態機冇嘅嘢）
• ${\displaystyle \mathrm {B} }$ 指一個空格，${\displaystyle \mathrm {B} \in \Gamma }$；（有限狀態機冇嘅嘢）
• ${\displaystyle F}$ 係部機嘅最終狀態；${\displaystyle F\subset S}$；
• ${\displaystyle \delta }$ 係狀態轉換函數，
  • ${\displaystyle \delta }$ 會指定「如果現時狀態係噉而輸入係噉，新狀態會係噉」嘅資訊：${\displaystyle \delta :S\times \Gamma \rightarrow S\times \Gamma \times \{{\text{L}},{\text{R}}\}}$，（同有限狀態機唔同嘅嘢）
  • 當中 ${\displaystyle {\text{L}}}$ 係指「將條帶向左郁」，${\displaystyle {\text{R}}}$ 係指「將條帶向右郁」。

圖靈機同有限狀態機最大嘅分別在於圖靈機能夠改變自己條「帶」上面嘅符號－即係可以好似典型嘅廿一世紀電腦噉，曉儲起同改變自己內部有嘅數據。因為呢個緣故，圖靈機有足夠嘅運算能力模擬嗮所有現代電腦做得到嘅運算，而有限狀態機做唔到呢樣嘢^[33]。

睇埋

• 運算理論
• 離散數學
• 程式編寫
• 模控學
• 控制理論
• 系統工程
• 行為樹
• 馬可夫鏈
• EDA
• 決策

文獻

基本入門：

• Carroll, J., Long, D., Theory of Finite Automata with an Introduction to Formal Languages. Prentice Hall, Englewood Cliffs, 1989.
• Cassandras, C., Lafortune, S., "Introduction to Discrete Event Systems". Kluwer, 1999, ISBN 0-7923-8609-4.
• Gill, A., Introduction to the Theory of Finite-state Machines. McGraw-Hill, 1962.
• Timothy Kam, Synthesis of Finite State Machines: Functional Optimization. Kluwer Academic Publishers, Boston 1997, ISBN 0-7923-9842-4.
• Kohavi, Z., Switching and Finite Automata Theory. McGraw-Hill, 1978.
• Tiziano Villa, Synthesis of Finite State Machines: Logic Optimization. Kluwer Academic Publishers, Boston 1997, ISBN 0-7923-9892-0
• Wagner, F., "Modeling Software with Finite State Machines: A Practical Approach", Auerbach Publications, 2006, ISBN 0-8493-8086-3.
• Wright, David R. (2005). "Finite State Machines" (PDF). CSC215 Class Notes. David R. Wright website, N. Carolina State Univ.

數學文獻：

• Booth, Taylor L. (1967). Sequential Machines and Automata Theory (1st ed.). New York: John Wiley and Sons, Inc. Library of Congress Card Catalog Number 67-25924.
• Brookshear, J. Glenn (1989). Theory of Computation: Formal Languages, Automata, and Complexity. Redwood City, California: Benjamin/Cummings Publish Company, Inc. ISBN 978-0-8053-0143-4.
• Davis, Martin; Sigal, Ron; Weyuker, Elaine J. (1994). Computability, Complexity, and Languages and Logic: Fundamentals of Theoretical Computer Science (2nd ed.). San Diego: Academic Press, Harcourt, Brace & Company. ISBN 978-0-12-206382-4.
• Hopcroft, John; Ullman, Jeffrey (1979). Introduction to Automata Theory, Languages, and Computation (1st ed.). Reading Mass: Addison-Wesley. ISBN 978-0-201-02988-8.

硬件文獻：

• Booth, Taylor L. (1967). Sequential Machines and Automata Theory (1st ed.). New York: John Wiley and Sons, Inc. Library of Congress Card Catalog Number 67-25924.
• Booth, Taylor L. (1971). Digital Networks and Computer Systems (1st ed.). New York: John Wiley and Sons, Inc. ISBN 978-0-471-08840-0.
• Hill, Fredrick J.; Peterson, Gerald R. (1965). Introduction to the Theory of Switching Circuits (1st ed.). New York: McGraw-Hill Book Company. Library of Congress Card Catalog Number 65-17394.
• McCluskey, E. J. (1965). Introduction to the Theory of Switching Circuits (1st ed.). New York: McGraw-Hill Book Company, Inc. Library of Congress Card Catalog Number 65-17394.

註釋

1. 簡單講就係一嚿有 5 個數嘅數學物體。
2. ${\displaystyle s_{0}\in S}$ 意思係 ${\displaystyle s_{0}}$ 喺 ${\displaystyle S}$ 入面（元素）。
3. 可以睇吓冪集。
4. ${\displaystyle A=\varnothing }$ 意思係 ${\displaystyle A}$ 係一個空集。
5. 要量度交通燈系統嘅「表現」，可以睇吓佢「有幾大機會搞到啲路塞車」。

引咗

1. Wang, Jiacun (2019). Formal Methods in Computer Science. CRC Press. p. 34.
2. "Finite State Machines – Brilliant Math & Science Wiki". brilliant.org.
3. Traffic Light Fsm.
4. Alrehily, A., Fallatah, R., & Thayananthan, V. (2015). Design of vending machine using finite state machine and visual automata simulator (PDF). International Journal of Computer Applications, 115(18), 37-42.
5. Monga, A., & Singh, B. (2012). Finite state machine based vending machine controller with auto-billing features (PDF). arXiv preprint arXiv:1205.3642.
6. Designing a simple game AI using Finite State Machines. Gamasutra.
7. Syahputra, M. F., Arippa, A., Rahmat, R. F., & Andayani, U. (2019, June). Historical theme game using finite state machine for actor behaviour (PDF). In Journal of Physics: Conference Series (Vol. 1235, No. 1, p. 012122). IOP Publishing.
8. Formal Definition of Finite State Machines.
9. Belzer, Jack; Holzman, Albert George; Kent, Allen (1975). Encyclopedia of Computer Science and Technology. 25. USA: CRC Press. p. 73.
10. Wright, David R. (2005). "Finite State Machines" (PDF). CSC215 Class Notes. David R. Wright website, N. Carolina State Univ.
11. Koshy, Thomas (2004). Discrete Mathematics With Applications. Academic Press. p. 762.
12. Taylor Booth (1967). Sequential Machines and Automata Theory, John Wiley and Sons, New York.
13. John Hopcroft and Jeffrey Ullman (1979). Introduction to Automata Theory, Languages, and Computation, Addison-Wesley Publishing Company, Reading Mass.
14. Lecture 9: Finite state machines. MATH 433.
15. A Simple Finite State Acceptor.
16. Jurafsky, Daniel (2009). Speech and Language Processing. Pearson.
17. Lecture Notes: Finite State Transducers.
18. Difference between Mealy machine and Moore machine. GeeksforGeeks.
19. Applications of Finite-State Transducers in Natural-Language Processing 互聯網檔案館嘅歸檔，歸檔日期2021年9月21號，.. web.stanford.edu.
20. Collobert, R., Weston, J., Bottou, L., Karlen, M., Kavukcuoglu, K., & Kuksa, P. (2011). Natural language processing (almost) from scratch. Journal of machine learning research, 12(Aug), 2493-2537.
21. Albat, Thomas Fritz. "Systems and Methods for Automatically Estimating a Translation Time." US Patent 0185235, 19 July 2012.
22. William Feller, An Introduction to Probability Theory and Its Applications, (Vol 1), 3rd Ed, (1968), Wiley.
23. Introduction to Nondeterministic Finite Automata (NFA). Medium.
24. Martin, John (2010). Introduction to Languages and the Theory of Computation. McGraw Hill. p. 108.
25. Finite State Machine Design (PDF). CSEE 3827: Fundamentals of Computer Systems.
26. Nath, S., Pal, C., Sau, S., Mukherjee, S., Roy, A., Guchhait, A., & Kandar, D. (2012, December). Design of an FPGA based intelligence traffic light controller with VHDL (PDF). In 2012 International Conference on Radar, Communication and Computing (ICRCC) (pp. 92-97). IEEE.
27. Wiseman, Y. (2016). Conceptual Design of Intelligent Traffic Light Controller. International Journal of Control and Automation, 9(7), 251-262.
28. Van Dinh, N., Ha, Y. G., & Kim, G. W. (2020, February). A Universal Control System for Self-Driving Car Towards Urban Challenges (PDF). In 2020 IEEE International Conference on Big Data and Smart Computing (BigComp) (pp. 452-454). IEEE.
29. Autonomous Vehicle Path Planning. Medium.
30. Orkin, J. (2006, March). Three states and a plan: the AI of FEAR. In Game Developers Conference (Vol. 2006, p. 4).
31. Gillies, M. (2009). Learning finite-state machine controllers from motion capture data (PDF). IEEE transactions on computational intelligence and AI in games, 1(1), 63-72.
32. Petzold, C. (2008). The annotated Turing: a guided tour through Alan Turing's historic paper on computability and the Turing machine. Wiley Publishing.
33. Basics of Automata Theory. Automata Theory.

拎

• （英文） "有限狀態機 - Brilliant Math & Science Wiki". brilliant.org.
• （英文） 用有限狀態機模擬簡單 AI 行為，講埋電子遊戲應用例子。
• （英文） 免費網上電腦詞典，有講 FSM 嘅概念。
• （英文） 有限狀態機嘅興起