有限狀態機

有限狀態機（粵拼：jau5 haan6 zong6 taai3 gei1，英文簡稱 FSM），又叫有限狀態自動機，係種運算模型。一部基本嘅有限狀態機會有呢啲部份：
若干（）個可能狀態，其中一個係部機開頭嗰陣嘅狀態（睇初始化）；
喺任何一個時間點 ，部有限狀態機會處於呢  個可能狀態當中嘅其中一個；而且
啲狀態係離散嘅，部機唔能夠同時處於多過一個狀態；
狀態可以因為外界嘅輸入而改變，而一部有限狀態機由一個狀態去另一個嘅過程就係一次轉換。
有限狀態機唔一定係決定嘅，如果話一部有限狀態機唔係決定，即係話部機帶有隨機，例：想像一部有限狀態機，有兩個可能狀態  同 ，當中  係開頭嗰陣嘅狀態；設計者可以將部機設計成「每當探測到光，就由  轉換去 」（決定），但又可以將部機設計成「每當探測到光，就有 50% 咁高嘅機會率由  轉換去 」（帶有隨機，所以唔係決定）。
好多廿一世紀初常見嘅機械都可以概念化想像成有限狀態機，例子有交通燈（紅燈、綠燈同黃燈三個狀態）同自動販賣機（一旦有客人入錢，就由「企喺度唔郁」狀態轉換成「將客人要嘅嘢放出嚟」狀態，放完變返「企喺度唔郁」）... 呀噉。除此之外，有限狀態機嘅技術喺廿一世紀初嘅電子遊戲 AI 領域上亦都成日用－遊戲製作師可以（例如）將遊戲入面嘅敵人角色設計成有限狀態機，有「企喺度唔郁」同埋（一旦同玩家角色之間嘅距離細過特定數值 ）「郁手攻擊玩家角色」等嘅狀態。

定義
幾部並排嘅閘機；閘機係一種簡單嘅有限狀態機，得兩個可能狀態－鎖咗同埋（因為有人入咗錢）開咗。
睇埋：運算模型、運算理論同相互遞歸
有限狀態機喺數學上定義係具有以下部份嘅五元組 ，當中：
係輸入（input）；
 係  個可能狀態嘅集合，，當中  係一個有限數值，而且 ；
 係部機嘅初始狀態（initial state），即係部機喺啱啱開機嗰陣嘅狀態，而  ；
 係狀態轉換函數（state-transition function），
 會指定「如果現時狀態係噉而輸入係噉，新狀態會係噉」嘅資訊：。
而如果部機係有隨機嘅， 會指定嘅係「如果現時狀態係噉而輸入係噉，進入每個新狀態嘅機會率會係噉」噉嘅資訊： 。
 可以係一個局部函數（partial function），意思即係話  唔使實要指定嗮每對可能「現時狀態」同「輸入」配對下嘅「新狀態」。
 係部機嘅最終狀態（final state），部機進入咗呢個狀態就唔會再改變狀態；。 可以係一個空集，意思即係話一部有限狀態機可以係冇最終狀態嘅。
有關呢啲數學概念嘅詳情，可以睇吓集合論相關嘅嘢。喺運算能力上，有限狀態機渣過圖靈機，即係話有啲運算問題係圖靈機解得到，但有限狀態機解唔到嘅。不過有限狀態機喺工程學上依然相當有用，可以用嚟將好多種機械概念化。

狀態圖
呢幅狀態圖描述一道門。
内文：狀態圖
喺電腦科學同相關領域上，研究者成日都會用有限狀態機嘅概念嚟做分析，而做分析嘅第一步通常係將部機以某啲形式表達出嚟。一般嚟講，表達有限狀態機嘅最直接方法係用狀態圖。一幅狀態圖會有以下嘅組成部份：
若干個節點（node），每個節點代表一個狀態，例如附圖嗰幅狀態圖描述嘅係一道門，道門有兩個狀態，開咗同閂埋咗，每個狀態喺幅圖入面係一個灰色嘅圓形；
若干個箭咀，每條箭咀表示一個可能嘅轉換，而且每條箭咀會掕住一啲字，描述轉換條件（transition condition），例如附圖，要由閂埋咗轉換去開咗，一個用家要做開門（open）嘅動作（轉換條件）；
指明邊一個狀態係初始狀態，例如附圖當中嘅「entry action」指住閂埋咗嘅狀態，表示閂埋咗嘅狀態係道門嘅初始狀態。
狀態圖唔一定會指明一部有限狀態機嘅狀態轉換函數，不過能夠有效噉將有限狀態機以視覺化嘅方式呈現出嚟，對於有限狀態機相關嘅研究嚟講好使好用。

接受機
内文：接受機
接受機（acceptor）做嘅工作係產生一個二元嘅輸出（1 定 0），用嚟表示個輸入係咪俾部機接受（所以叫接受機），數學啲噉講，一部有限狀態機嘅狀態當中有一部份會係所謂嘅接受狀態（），，而部機嘅初始狀態可以係一個接受狀態，接受機輸入通常會係一串符號，可以用嚟運算一串符號係咪設計想要嘅。舉個例說明，想像以下嘅有限狀態機，部機會攞一串字做輸入，將串字逐個逐個睇，如果串字係英文字詞 nice，噉部機最後會達到成功嘅狀態，而呢個狀態係部機唯一一個接受狀態，如果串字唔夾，噉部機會進入出錯嘅狀態：
接受機一個常見用途係攞嚟處理語言，不過接受機亦都可以用嚟處理數字方面嘅運算，例如以下呢部噉嘅接受機可以用嚟睇一個數係咪 3 嘅倍數：想像串輸入係 1001 －呢串嘢係一個用二進制寫嘅數字，等同於十進制當中嘅 9，部機會將個數字嘅位由細嘅做起始、逐個逐個睇，1001 呢串嘢如果入落去以下嘅接受機嗰度，會令部機經過以下嘅連串狀態：
－最後處於  呢個接受狀態（呢個接受狀態表示個數係 3 嘅倍數）。

傳感機
内文：有限狀態傳感機
有限狀態傳感機（finite-state transducer，FST）會好似圖靈機噉有一條輸入帶同一條輸出帶：一般嘅有限狀態機淨係曉按輸入改變自己嘅狀態，頂櫳做到以「自己嘅狀態」直接攞嚟做輸出；而相比之下，一部有限狀態傳感機會按輸入改變自己嘅狀態，而輸出會係「部機嘅狀態」嘅函數（輸出函數，），即係話輸出取決於「部機嘅狀態」。而用數學行話嚟講嘅話，有限狀態傳感機可以話係有限狀態機嘅一種廣義化－有限狀態機可以當係「 係一個恆等函數」嘅有限狀態傳感機。
好似係下圖呢部機噉，狀態（啲圓形）之間可以轉換（箭咀），而一個箭咀掕住嘅符號係指「部機喺經歷呢個轉換嗰陣會出嘅符號」，例如由 code 去 slash 再去 block 嘅過程會出 /*。
有限狀態傳感機仲可以再細分做兩種：
摩亞機，指輸出完全由部機嘅狀態話事，同埋
美利機，指輸出同時由部機嘅狀態以及輸入話事。
有限狀態傳感機喺自然語言處理（NLP）上成日會用到。自然語言處理泛指教人工智能處理自然語言嘅工作，好似係機械翻譯噉，機翻研究點樣用電腦軟件嚟幫手翻譯一啲用自然語言寫嘅文字，而一個程式做翻譯嗰陣，個程式要識睇嗮成句句子，甚至乎係成段嘢，了解當中每個字嘅意思先決定俾乜嘢輸出。可以睇埋遞迴神經網絡嘅嘢。

按決定性嚟分
内文：決定型有限狀態機同非決定型有限狀態機
有限狀態機嘅一個重要分類準則係「係咪帶有隨機」：喺數學上，隨機大致上可以定義做「本質上唔能夠完美噉預測嘅嘢」，現實例子有掟銀仔同擲骰仔等嘅現象，而概率論等嘅數學理論有詳細探討隨機相關嘅問題；決定型有限狀態機係指完全決定嘅有限狀態機，柞  會指明要去邊一個狀態，而非決定型有限狀態機就啱啱相反，唔完全決定，一部非決定型有限狀態機嘅  會掕住機會率（反映一件事有幾大機會發生）數值，講明（例如）「如果喺呢個呢個狀態（）接收到  噉嘅輸入，有  咁大機會去 、 咁大機會去 ...」等嘅資訊。
例如以下呢部有限狀態機就係非決定型嘅，由狀態  接收到輸入「1」可以去  或者去 。

交通燈
内文：交通燈
交通燈係另一種成日俾人攞嚟做有限狀態機嘅例子嘅機械。想像以下嘅簡單例子：家陣有個十字路口，（上當係北）一條打橫嘅馬路（）同一條打戙嘅馬路（）喺呢個十字路口相交（可以睇吓下圖），而啲車淨係可以去對面條路－由北面嚟嘅車淨係可以向南面駛、由西面嚟嘅車淨係可以向東面駛... 如此類推；而家有個工程師，佢需要設計點樣擺低一啲交通燈嚟控制呢個十字路口嘅車流，呢兩個十字路口嘅交通燈可以想像成有四個狀態嘅有限狀態機（），而喺最簡單嘅情況下，呢部有限狀態機會每隔一段特定長度嘅時間就跳去下一個狀態（「」表示「 咁耐嘅時間過咗」）：
， 綠燈、 紅燈，呢個係初始狀態（）；
， 黃燈、 紅燈；
， 紅燈、 綠燈；
， 紅燈、 黃燈；
呢部有限狀態機並冇最終狀態， 。
想像中嘅十字路口由上空望嘅圖解
土木工程同城市規劃等領域嘅工作者會花好多時間精神諗交通燈系統嘅設計：一個城市嘅順利運作相當有賴於車流嘅控制；車流控制得唔好會搞到啲路出現塞車嘅情況，塞車會阻礙啲人返工或者運送貨品，而呢啲活動受阻會搞到個城市嘅生產變慢，對經濟有負面嘅影響；因為噉，相關嘅工程學領域抌好多資源研究點樣改善交通燈系統嘅設計，呢啲研究往往會將交通燈系統想像成有限狀態機，然後再用電腦模擬「假設啲司機按正常方法揸車（見到紅燈就停車、係綠燈就踩油...）嘅話，呢個噉嘅路口（路口有好多唔同種類）同呢個噉嘅交通燈系統結合埋會產生點樣嘅車流」，並且靠噉嚟比較唔同交通燈系統嘅表現。

自駕車
一架自駕車行嘅片
内文：自駕車
自駕車係指唔使人特登操作都曉行去目的地嘅汽車，通常會用到人工智能（AI）技術。而家假想有架自駕車，佢內置咗適當嘅感應器同相關嘅人工智能技術（可以睇吓電腦視覺），令個人工智能識得正確噉判斷自己身處喺乜嘢情況入面－可能嘅情況包括咗「身處十字路口」、「身處高速公路」同埋「身處停車場」呀噉；而個人工智能可以設成一部有限狀態機，每個呢啲情況做一個狀態，跟住再編寫類似以下噉嘅程式，以下呢個程式教架車判斷周圍每一架車喺條路嘅邊條線：
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;
    }
  }
直去緊、要掟彎同埋見到紅燈等嘅狀態之間可以按類似嘅原理想像。

電子遊戲應用
睇埋：電子遊戲 AI
喺電子遊戲人工智能上，有限狀態機可以用嚟教遊戲嘅 NPC 做決策：電子遊戲好多時會涉及由電腦控制、同玩家進行對局嘅角色，遊戲開發者為咗想玩家得到樂趣，通常會想呢啲由電腦控制嘅角色有返咁上下聰明，能夠為玩家提供一定嘅挑戰，即係話佢哋會想 NPC 展現一定程度嘅智能，而有智能嘅物體係理應要曉做決策嘅。
直至廿一世紀初為止，有限狀態機依然係其中一種最多人用嘅遊戲 AI 做法例如想像一個寫嚟教電腦玩射擊遊戲嘅 AI，個 AI 係一部有限狀態機，有防守、進攻同去搵彈藥等多個可能狀態，佢內置嘅 AI 演算法就要教佢幾時進入邊個狀態（例：if 自己淨低嘅生命值低過 50%，then 進入防守狀態－教佢喺自己血低嗰陣要防守）。呢類決策演算法會攞同遊戲輸贏相關嘅資訊（自己同對手血量等等），並且計出要進入邊個狀態（採取邊個策略）。有限狀態機同搵路呢兩個概念係遊戲 AI 嘅基礎。
一個以有限狀態機形式存在嘅遊戲 AI 望落會有類似噉嘅碼：
void Update(){ // 呢段碼教一個 AI 玩揸戰機。
  switch(state){ // 視乎 state（狀態）係乜，做...
    case State.PURSUIT: // 如果狀態係 pursuit（追擊）嘅話，做...
      CheckForDanger(); // 一個睇吓周圍有冇危險嘅子程序
      Chase(target, true); // 追目標；呢個子程序當中會有演算法，決定幾時要將 state 呢個變數改變並且離開個子程序。
      break;

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

同圖靈機對比
睇埋：圖靈機
理論上，有限狀態機嘅運算能力可以話係渣過圖靈機。圖靈機係另一種運算理論上成日討論嘅運算模型。用言語講嘅話，一部圖靈機嘅運作方式如下：一部圖靈機會讀取一條分做若干個格嘅帶，條帶每個格裏面都會有個符號（可以係 1 同 0 等多個款）；喺每一個時間點，部圖靈機個讀取器都會位於條帶其中一格，而部機就會做以下三個基本作業當中任何一個：
讀取讀取器下嗰格係乜符號；
編輯嗰格－寫一個新嘅符號落去或者刪除咗嗰格佢；
將條帶向左或者向右移一格，等個讀取器可以讀取打前嗰個格隔離嘅一個格。
圖靈機嘅想像圖如下：
圖靈機又可以想像成具有以下部份嘅物體：
係  個可能狀態，，當中  係一個有限數值，而且 ；
 係部機嘅初始狀態，即係部機喺啱啱開機嗰陣嘅狀態，而 ；
 係輸入（input）；
 指容許嘅輸入符號嘅集合，而呢個集合係有限嘅；（有限狀態機冇嘅嘢）
 指一個空格，；（有限狀態機冇嘅嘢）
 係部機嘅最終狀態；；
 係狀態轉換函數，
 會指定「如果現時狀態係噉而輸入係噉，新狀態會係噉」嘅資訊：，（同有限狀態機唔同嘅嘢）
當中  係指「將條帶向左郁」， 係指「將條帶向右郁」。
圖靈機同有限狀態機最大嘅分別在於圖靈機能夠改變自己條「帶」上面嘅符號－即係可以好似典型嘅廿一世紀電腦噉，曉儲起同改變自己內部有嘅數據。因為呢個緣故，圖靈機有足夠嘅運算能力模擬嗮所有現代電腦做得到嘅運算，而有限狀態機做唔到呢樣嘢。