有限狀態機

又叫有限狀態自動機係種運算模型。一部基本嘅有限狀態機會有呢啲部份：
若干個可能狀態，其中一個係部機開頭嗰陣嘅狀態；
喺任何一個時間點 ，部有限狀態機會處於呢  個可能狀態當中嘅其中一個；而且
啲狀態係離散嘅，部機唔能夠同時處於多過一個狀態；
狀態可以因為外界嘅輸入而改變，而一部有限狀態機由一個狀態去另一個嘅過程就係一次轉換。
有限狀態機唔一定係決定嘅，如果話一部有限狀態機唔係決定，即係話部機帶有隨機，例：想像一部有限狀態機，有兩個可能狀態  同 ，當中  係開頭嗰陣嘅狀態；設計者可以將部機設計成「每當探測到光，就由  轉換去 」，但又可以將部機設計成「每當探測到光，就有 50% 咁高嘅機會率由  轉換去 」。

好多廿一世紀初常見嘅機械都可以概念化想像成有限狀態機，例子有交通燈同自動販賣機... 呀噉。除此之外，有限狀態機嘅技術喺廿一世紀初嘅電子遊戲 AI 領域上亦都成日用－遊戲製作師可以將遊戲入面嘅敵人角色設計成有限狀態機，有「企喺度唔郁」同埋「郁手攻擊玩家角色」等嘅狀態。

定義 

有限狀態機喺數學上定義係具有以下部份嘅五元組 ，當中：
 係輸入；
 係  個可能狀態嘅集合，，當中  係一個有限數值，而且 ；
 係部機嘅初始狀態，即係部機喺啱啱開機嗰陣嘅狀態，而  ；
 係狀態轉換函數，
 會指定「如果現時狀態係噉而輸入係噉，新狀態會係噉」嘅資訊：。
而如果部機係有隨機嘅， 會指定嘅係「如果現時狀態係噉而輸入係噉，進入每個新狀態嘅機會率會係噉」噉嘅資訊： 。
 可以係一個局部函數，意思即係話  唔使實要指定嗮每對可能「現時狀態」同「輸入」配對下嘅「新狀態」。
 係部機嘅最終狀態，部機進入咗呢個狀態就唔會再改變狀態；。 可以係一個空集，意思即係話一部有限狀態機可以係冇最終狀態嘅。
有關呢啲數學概念嘅詳情，可以睇吓集合論相關嘅嘢。喺運算能力上，有限狀態機渣過圖靈機，即係話有啲運算問題係圖靈機解得到，但有限狀態機解唔到嘅。不過有限狀態機喺工程學上依然相當有用，可以用嚟將好多種機械概念化。
例子
好似閘機就係一個簡單嘅例子：閘機係一種喺車站同遊樂園入口等嘅地方成日見到嘅機械，通常到大人嘅腰咁高，用途係要確保啲人要俾錢先至可以通過；一部基本嘅閘機會有
兩個狀態－「鎖咗」同「開咗」，當中前者係初始狀態；
喺「鎖咗」嘅狀態下，部閘機嘅柄喺鎖死咗郁唔到嘅，但一旦有人俾咗「入銀仔」嘅輸入，部閘機會轉換成「開咗」嘅狀態；
喺「開咗」嘅狀態下，部閘機嘅柄轉得郁，而如果啲柄俾人到轉咗一個圈，部閘機會返去「鎖咗」嘅狀態；
喺「鎖咗」嘅狀態下，部閘機嘅柄俾人點㧬都唔會郁，狀態會唔變；
喺「開咗」嘅狀態下，就算有人入銀仔，狀態依然會唔變；
如果將上述講嘅嘢畫成理想化嘅圖解嘅話會係噉：

表達 

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

分類

接受機 

接受機做嘅工作係產生一個二元嘅輸出，用嚟表示個輸入係咪俾部機接受，數學啲噉講，一部有限狀態機嘅狀態當中有一部份會係所謂嘅接受狀態，，而部機嘅初始狀態可以係一個接受狀態，接受機輸入通常會係一串符號，可以用嚟運算一串符號係咪設計想要嘅。舉個例說明，想像以下嘅有限狀態機，部機會攞一串字做輸入，將串字逐個逐個睇，如果串字係英文字「nice」，噉部機最後會達到「success」嘅狀態，而呢個狀態係部機唯一一個接受狀態，如果串字唔夾，噉部機會進入「error」嘅狀態：

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

－最後處於  呢個接受狀態。

傳感機 

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

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

有限狀態傳感機仲可以再細分做兩種：
摩亞機，指輸出完全由部機嘅狀態話事，同埋
美利機，指輸出同時由部機嘅狀態以及輸入話事。

語言處理 

有限狀態傳感機喺自然語言處理上成日會用到。自然語言處理泛指教人工智能程式處理自然語言嘅工作，好似係機械翻譯噉，機翻研究點樣用電腦軟件嚟幫手翻譯一啲用自然語言寫嘅文字，而一個程式做翻譯嗰陣，個程式要識睇嗮成句句子，甚至乎係成段嘢，了解當中每個字嘅意思先決定俾乜嘢輸出。舉個簡單嘅例子，以下有兩句英文句子：
句子 1：The horror novel is disturbing.
句子 2：The noises he makes are disturbing.
喺以上呢兩句句子裏面，講緊嘢嗰個人都用咗「disturbing」呢個形容詞，但呢個字要譯做粵文嘅話就起碼有兩個可能嘅意思：呢個字就噉睇可以譯做「令人不安」，但譯做「令人覺得佢煩」又得，所以對於呢個字要點譯，就一定要睇嗮成句句子先可以做決定：句子 1 用「disturbing」嚟形容一本恐怖小說，而句子 2 就用「disturbing」嚟形容某個人所發出嘅噪音。一般會認為喺前者嘅情況當中，「disturbing」比較可能係指「令人不安」，而喺後者嘅情況入面，呢個字就比較可能係指「令人覺得佢煩」－一個字嘅意思可能會因為打前嘅字而有所不同。

有限狀態傳感機可以用嚟教人工智能處理上文下理：舉個好簡單嘅例子，想像一部以有限狀態傳感機型式整、英譯粵嘅機翻程式，佢一讀到「horror novel」或者類似意思嘅英文字就會進入狀態 、一讀到「noise」或者類似意思嘅英文字就會進入狀態 ，而一旦喺  嗰度讀到「distrubing」就出「令人不安」，喺  嗰度讀到「distrubing」就出「令人覺得佢煩」。有關處理上文下理嘅問題，可按決定性分 

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

例如以下呢部有限狀態機就係非決定性嘅，由狀態  接收到輸入「1」可以去  或者去 。

工程分析 

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

交通燈 

交通燈係另一種成日俾人攞嚟做有限狀態機嘅例子嘅機械。想像以下嘅簡單例子：家陣有個十字路口，一條打橫嘅馬路同一條打戙嘅馬路喺呢個十字路口相交，而啲車淨係可以去對面條路－由北面嚟嘅車淨係可以向南面駛、由西面嚟嘅車淨係可以向東面駛... 如此類推；而家有個工程師，佢需要設計點樣擺低一啲交通燈嚟控制呢個十字路口嘅車流，呢兩個十字路口嘅交通燈可以想像成有四個狀態嘅有限狀態機，而喺最簡單嘅情況下，呢部有限狀態機會每隔一段特定長度嘅時間就跳去下一個狀態：
， 、 ，呢個係初始狀態；
， 、 ；
， 、 ；
， 、 ；
呢部有限狀態機並冇最終狀態， 。

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

自駕車 

自駕車係指唔使人特登操作都曉行去目的地嘅汽車，通常會用到人工智能技術。而家假想有架自駕車，佢內置咗適當嘅感應器同相關嘅人工智能技術，令個人工智能識得正確噉判斷自己身處喺乜嘢情況入面－可能嘅情況包括咗「身處十字路口」、「身處高速公路」同埋「身處停車場」呀噉；而個人工智能可以設成一部有限狀態機，每個呢啲情況做一個狀態，跟住再編寫類似以下噉嘅程式，以下呢個程式教架車判斷周圍每一架車喺條路嘅邊條線：
if (d > 0 && d < 4) // d 表示架車嘅打橫坐標，單位係米，當中「0」表示條路左面嗰條邊嘅坐標。
  {
    car_lane = 0; // 如果有架車嘅 d 係 0 - 4 米，噉佢係身處喺左邊條線
  } else if (d > 4 && d < 8) {
    car_lane = 1; // ... 噉佢係身處喺中間條線
  } else if (d > 8 && d < 12) {
    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;
    }
  }
「直去緊」、「要掟彎」同埋「見到紅燈」等嘅狀態之間可以按類似嘅原理想像。

電子遊戲應用 

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

直至廿一世紀初為止，有限狀態機依然係其中一種最多人用嘅遊戲 AI 做法例如想像一個寫嚟教電腦玩射擊遊戲嘅 AI，個 AI 係一部有限狀態機，有「防守」、「進攻」同「去搵彈藥」等多個可能狀態，佢內置嘅 AI 演算法就要教佢幾時進入邊個狀態。呢類決策演算法會攞同遊戲輸贏相關嘅資訊，並且計出要進入邊個狀態。有限狀態機同搵路呢兩個概念係遊戲 AI 嘅基礎。
例子碼
一個以有限狀態機形式存在嘅遊戲 AI 望落會有類似噉嘅碼：
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; // 離開子程序，令個程式返到去揀狀態嘅點。
  }

同圖靈機對比 

理論上，有限狀態機嘅運算能力可以話係渣過圖靈機。圖靈機係另一種運算理論上成日討論嘅運算模型。用言語講嘅話，一部圖靈機嘅運作方式如下：一部圖靈機會讀取一條分做若干個格嘅帶，條帶每個格裏面都會有個符號；喺每一個時間點，部圖靈機個讀取器都會位於條帶其中一格，而部機就會做以下三個基本作業當中任何一個：
讀取讀取器下嗰格係乜符號；
編輯嗰格－寫一個新嘅符號落去或者刪除咗嗰格佢；
將條帶向左或者向右移一格，等個讀取器可以讀取打前嗰個格隔離嘅一個格。
圖靈機嘅想像圖如下：

圖靈機又可以想像成具有以下部份嘅物體：
 係  個可能狀態，，當中  係一個有限數值，而且 ；
 係部機嘅初始狀態，即係部機喺啱啱開機嗰陣嘅狀態，而 ；
 係輸入；
 指容許嘅輸入符號嘅集合，而呢個集合係有限嘅；
 指一個空格，；
 係部機嘅最終狀態
 係狀態轉換函數，
 會指定「如果現時狀態係噉而輸入係噉，新狀態會係噉」嘅資訊：，
當中  係指「將條帶向左郁」， 係指「將條帶向右郁」。
圖靈機同有限狀態機最大嘅分別在於圖靈機能夠改變自己條「帶」上面嘅符號－即係可以好似典型嘅廿一世紀電腦噉，曉儲起同改變自己內部有嘅數據。因為呢個緣故，圖靈機有足夠嘅運算能力模擬嗮所有現代電腦做得到嘅運算，而有限狀態機做唔到呢樣嘢。

運算理論
離散數學
程式編寫
模控學
控制理論
系統工程
行為樹
馬可夫鏈
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.
Ginsburg, S., An Introduction to Mathematical Machine Theory. Addison-Wesley, 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.
Sakarovitch, Jacques (2009). Elements of automata theory. Translated from the French by Reuben Thomas. Cambridge University Press. ISBN 978-0-521-84425-3. Zbl 1188.68177.
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.

數學文獻 

Arbib, Michael A. (1969). Theories of Abstract Automata (1st ed.). Englewood Cliffs, N.J.: Prentice-Hall, Inc. ISBN 978-0-13-913368-8.
Bobrow, Leonard S.; Arbib, Michael A. (1974). Discrete Mathematics: Applied Algebra for Computer and Information Science (1st ed.). Philadelphia: W. B. Saunders Company, Inc. ISBN 978-0-7216-1768-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.
Boolos, George; Jeffrey, Richard (1999) [1989]. Computability and Logic (3rd ed.). Cambridge, England: Cambridge University Press. ISBN 978-0-521-20402-6.
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.
Hopcroft, John E.; Motwani, Rajeev; Ullman, Jeffrey D. (2001). Introduction to Automata Theory, Languages, and Computation (2nd ed.). Reading Mass: Addison-Wesley. ISBN 978-0-201-44124-6.
Hopkin, David; Moss, Barbara (1976). Automata. New York: Elsevier North-Holland. ISBN 978-0-444-00249-5.
Kozen, Dexter C. (1997). Automata and Computability (1st ed.). New York: Springer-Verlag. ISBN 978-0-387-94907-9.
Lewis, Harry R.; Papadimitriou, Christos H. (1998). Elements of the Theory of Computation (2nd ed.). Upper Saddle River, New Jersey: Prentice-Hall. ISBN 978-0-13-262478-7.
Linz, Peter (2006). Formal Languages and Automata (4th ed.). Sudbury, MA: Jones and Bartlett. ISBN 978-0-7637-3798-6.
Minsky, Marvin (1967). Computation: Finite and Infinite Machines (1st ed.). New Jersey: Prentice-Hall.
Papadimitriou, Christos (1993). Computational Complexity (1st ed.). Addison Wesley. ISBN 978-0-201-53082-7.
Pippenger, Nicholas (1997). Theories of Computability (1st ed.). Cambridge, England: Cambridge University Press. ISBN 978-0-521-55380-3.
Rodger, Susan; Finley, Thomas (2006). JFLAP: An Interactive Formal Languages and Automata Package (1st ed.). Sudbury, MA: Jones and Bartlett. ISBN 978-0-7637-3834-1.
Sipser, Michael (2006). Introduction to the Theory of Computation (2nd ed.). Boston Mass: Thomson Course Technology. ISBN 978-0-534-95097-2.
Wood, Derick (1987). Theory of Computation (1st ed.). New York: Harper & Row, Publishers, Inc. ISBN 978-0-06-047208-5.

硬件文獻 

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.

攷

拎 

"Finite State Machines – Brilliant Math & Science Wiki". brilliant.org.
Modeling a Simple AI behavior using a Finite State Machine. Example of usage in Video Games.
Free On-Line Dictionary of Computing description of Finite-State Machines.
NIST Dictionary of Algorithms and Data Structures description of Finite-State Machines.
A brief overview of state machine types, comparing theoretical aspects of Mealy, Moore, Harel & UML state machines.
The Rise Of The State Machines.

運算理論
機械