呢篇文係一篇好文。想知更多,請撳呢個掣。

有限狀態機

出自維基百科,自由嘅百科全書
跳去導覽 跳去搵嘢

交通燈有三個可能狀態-紅燈黃燈綠燈

有限狀態機粵拼jau5 haan6 zong6 taai3 gei1英文finite-state machineFSM),又或者叫做有限狀態自動機finite-state automatonFSA)係一種運算模型。一部基本嘅有限狀態機會有呢啲部份:

  • 若干()個可能狀態,其中一個係部機開頭嗰陣嘅狀態(睇初始化);
  • 喺任何一個時間點 ,部有限狀態機會處於呢 個可能狀態當中嘅其中一個;而且
  • 啲狀態係離散(discrete)嘅,部機能夠同時處於多過一個狀態;
  • 狀態可以因為外界嘅輸入而改變,而一部有限狀態機由一個狀態去另一個嘅過程就係一次轉換(transition)[1]

有限狀態機唔一定係決定性(deterministic)嘅,如果話一部有限狀態機唔係決定性,即係話部機帶有隨機性,例:想像一部有限狀態機,有兩個可能狀態 ,當中 係開頭嗰陣嘅狀態;設計者可以將部機設計成「每當探測,就由 轉換去 」(決定性),但又可以將部機設計成「每當探測到光,就有 50% 咁高嘅機會率 轉換去 」(帶有隨機性,所以唔係決定性)[2]

DFAexample.svg

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

定義[編輯]

幾部並排嘅閘機;閘機係一種簡單嘅有限狀態機,得兩個可能狀態-「鎖咗」同埋(因為有人入咗錢)「開咗」。

有限狀態機喺數學定義係具有以下部份嘅五元組[註 1],當中[2][8]

  • 輸入(input);
  • 個可能狀態嘅集合,當中 係一個有限數值,而且
  • 係部機嘅初始狀態(initial state),即係部機喺啱啱開機嗰陣嘅狀態,而 [註 2]
  • 狀態轉換函數(state-transition function),
    • 會指定「如果現時狀態係噉而輸入係噉,新狀態會係噉」嘅資訊
    • 而如果部機係有隨機性嘅, 會指定嘅係「如果現時狀態係噉而輸入係噉,進入每個新狀態嘅機會率會係噉」噉嘅資訊: [註 3]
    • 可以係一個局部函數(partial function),意思即係話 唔使實要指定嗮每對可能「現時狀態」同「輸入」配對下嘅「新狀態」。
  • 係部機嘅最終狀態(final state),部機進入咗呢個狀態就唔會再改變狀態; 可以係一個空集(empty set),意思即係話一部有限狀態機可以係冇最終狀態嘅。

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

例子

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

  • 兩個狀態()-「鎖咗」(locked;)同「開咗」(unlocked;),當中前者係初始狀態;
  • 喺「鎖咗」嘅狀態下,部閘機嘅柄喺鎖死咗郁唔到嘅,但一旦有人俾咗「入銀仔」嘅輸入(),部閘機會轉換成「開咗」嘅狀態();
  • 喺「開咗」嘅狀態下,部閘機嘅柄轉得郁,而如果啲柄俾人推到轉咗一個圈(),部閘機會返去「鎖咗」嘅狀態();
  • 喺「鎖咗」嘅狀態下,部閘機嘅柄俾人點推都唔會郁,狀態會唔變();
  • 喺「開咗」嘅狀態下,就算有人入銀仔,狀態依然會唔變();

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

Turnstile state machine colored.svg

表達[編輯]

呢幅狀態圖描述一道
內文:狀態圖

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

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

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

分類[編輯]

睇埋:自動機理論

接受機[編輯]

內文:接受機

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

Fsm parsing word nice.svg

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

-最後處於 呢個接受狀態(呢個接受狀態表示「個數係 3 嘅倍數」)[13]

DFA example multiplies of 3.svg

傳感機[編輯]

內文:有限狀態傳感機

有限狀態傳感機(finite-state transducer,FST)會好似圖靈機(Turing machine)噉有一條輸入帶(input tape)同一條輸出帶(output tape):一般嘅有限狀態機淨係曉按輸入改變自己嘅狀態,頂櫳做到以「自己嘅狀態」直接攞嚟做輸出;而相比之下,一部有限狀態傳感機會按輸入改變自己嘅狀態,而輸出會係「部機嘅狀態」嘅函數(輸出函數;output function,),即係話輸出取決於「部機嘅狀態」。而用數學行話嚟講嘅話,有限狀態傳感機可以話係有限狀態機嘅一種廣義化(generalization)-有限狀態機可以當係「 係一個恆等函數」嘅有限狀態傳感機[16][17]

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

Finite-state-transducer-comments.png

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

  • 摩亞機(Moore machine),指輸出完全由部機嘅狀態話事,同埋
  • 美利機(Mealy machine),指輸出同時由部機嘅狀態以及輸入話事。

語言處理[編輯]

睇埋:自然語言處理同埋機械翻譯

有限狀態傳感機喺自然語言處理(natural language processing,NLP)上成日會用到[19]。自然語言處理泛指教人工智能程式處理自然語言嘅工作[20],好似係機械翻譯(machine translation)噉,機翻研究點樣用電腦軟件嚟幫手翻譯一啲用自然語言寫嘅文字,而一個程式做翻譯嗰陣,個程式要識睇嗮成句句子,甚至乎係成段嘢,了解當中每個字嘅意思先決定俾乜嘢輸出[21]。舉個簡單嘅例子,以下有兩句英文句子:

句子 1:The horror novel is disturbing.
句子 2:The noises he makes are disturbing.

喺以上呢兩句句子裏面,講緊嘢嗰個人都用咗「disturbing」呢個形容詞,但呢個字要譯做粵文嘅話就起碼有兩個可能嘅意思:呢個字就噉睇可以譯做「令人不安」,但譯做「令人覺得佢煩」又得[22],所以對於呢個字要點譯,就一定要睇嗮成句句子先可以做決定:句子 1 用「disturbing」嚟形容一本恐怖小說,而句子 2 就用「disturbing」嚟形容某個人所發出嘅噪音。一般會認為喺前者嘅情況當中,「disturbing」比較可能係指「令人不安」,而喺後者嘅情況入面,呢個字就比較可能係指「令人覺得佢煩」-一個字嘅意思可能會因為打前嘅字而有所不同[23]

有限狀態傳感機可以用嚟教人工智能處理上文下理:舉個好簡單嘅例子,想像一部以有限狀態傳感機型式整、英譯粵嘅機翻程式,佢一讀到「horror novel」或者類似意思嘅英文字就會進入狀態 、一讀到「noise」或者類似意思嘅英文字就會進入狀態 ,而一旦喺 嗰度讀到「distrubing」就出「令人不安」,喺 嗰度讀到「distrubing」就出「令人覺得佢煩」[19]。有關處理上文下理嘅問題,可以睇埋遞迴神經網絡

按決定性分[編輯]

內文:決定性有限狀態機非決定性有限狀態機

有限狀態機另一個重要分類準則係「係咪帶有隨機性」:喺數學上,隨機性大致上可以定義做「本質上唔能夠完美噉預測嘅嘢」,現實例子有掟銀仔擲骰仔等嘅現象,而概率論(probability theory)等嘅數學理論有詳細探討隨機性相關嘅問題[24]決定性有限狀態機(deterministic FSM)係指完全冇隨機性嘅有限狀態機,柞 會指明要去邊一個狀態,而非決定性有限狀態機(non-deterministic FSM)就啱啱相反,會帶啲隨機性喺入面,一部非決定性有限狀態機嘅 會掕住機會率(probability;反映一件事有幾大機會發生嘅數值)數值,講明(例如)「如果喺呢個呢個狀態()接收到 噉嘅輸入,有 咁大機會去 咁大機會去 ...」等嘅資訊[25][26]

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

NFASimpleExample.svg

工程分析[編輯]

睇埋:機械同埋系統

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

交通燈[編輯]

內文:交通燈

交通燈(traffic light)係另一種成日俾人攞嚟做有限狀態機嘅例子嘅機械[3]。想像以下嘅簡單例子:家陣有個十字路口,(「上」當係「北」)一條打橫嘅馬路)同一條打戙嘅馬路()喺呢個十字路口相交(可以睇吓下圖),而啲車淨係可以去對面條路-由北面嚟嘅車淨係可以向南面駛、由西面嚟嘅車淨係可以向東面駛... 如此類推;而家有個工程師,佢需要設計點樣擺低一啲交通燈嚟控制呢個十字路口嘅車流,呢兩個十字路口嘅交通燈可以想像成有四個狀態嘅有限狀態機(),而喺最簡單嘅情況下,呢部有限狀態機會每隔一段特定長度嘅時間就跳去下一個狀態(「」表示「 咁耐嘅時間過咗」)[27]

  • 綠燈 紅燈,呢個係初始狀態();
  • 黃燈 紅燈
  • 紅燈 綠燈
  • 紅燈 黃燈
  • 呢部有限狀態機並冇最終狀態, [註 4]
想像中嘅十字路口由上空望嘅圖解

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

自駕車[編輯]

一架自駕車行嘅片
內文:自駕車

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

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;
    }
  }

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

電子遊戲應用[編輯]

睇埋:電子遊戲 AI

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

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

例子碼

一個以有限狀態機形式存在嘅遊戲 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; // 離開子程序,令個程式返到去揀狀態嘅點。
  }

同圖靈機對比[編輯]

睇埋:圖靈機

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

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

圖靈機嘅想像圖如下:

Maquina.png

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

  • 個可能狀態,,當中 係一個有限數值,而且
  • 係部機嘅初始狀態(initial state),即係部機喺啱啱開機嗰陣嘅狀態,而
  • 輸入(input);
  • 指容許嘅輸入符號嘅集合,而呢個集合係有限嘅;(有限狀態機冇嘅嘢)
  • 指一個空格(blank),;(有限狀態機冇嘅嘢)
  • 係部機嘅最終狀態(final state);
  • 狀態轉換函數(state-transition function),
    • 會指定「如果現時狀態係噉而輸入係噉,新狀態會係噉」嘅資訊,(同有限狀態機唔同嘅嘢)
    • 當中 係指「將條帶向左郁」, 係指「將條帶向右郁」。

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

註釋[編輯]

  1. 簡單講就係一嚿有 5 個嘅數學物體。
  2. 」意思係「 入面」(元素)。
  3. 可以睇吓冪集
  4. 」意思係「 係一個空集」。
  5. 交通燈系統嘅「表現」可以用「有幾大機會搞到啲路塞車」等嘅指標量度。

睇埋[編輯]

文獻[編輯]

基本入門[編輯]

  • 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.

[編輯]

  1. Wang, Jiacun (2019). Formal Methods in Computer Science. CRC Press. p. 34.
  2. 2.0 2.1 "Finite State Machines – Brilliant Math & Science Wiki". brilliant.org.
  3. 3.0 3.1 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. 6.0 6.1 6.2 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. 10.0 10.1 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. 13.0 13.1 13.2 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. 19.0 19.1 Applications of Finite-State Transducers in Natural-Language Processing. 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. Definition of 'disturbing'. Collins English Dictionary.
  23. Importance of Context in Translation.
  24. William Feller, An Introduction to Probability Theory and Its Applications, (Vol 1), 3rd Ed, (1968), Wiley.
  25. Introduction to Nondeterministic Finite Automata (NFA). Medium.
  26. Martin, John (2010). Introduction to Languages and the Theory of Computation. McGraw Hill. p. 108.
  27. Finite State Machine Design (PDF). CSEE 3827: Fundamentals of Computer Systems.
  28. 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.
  29. Wiseman, Y. (2016). Conceptual Design of Intelligent Traffic Light Controller. International Journal of Control and Automation, 9(7), 251-262.
  30. 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.
  31. 31.0 31.1 Autonomous Vehicle Path Planning. Medium.
  32. Orkin, J. (2006, March). Three states and a plan: the AI of FEAR. In Game Developers Conference (Vol. 2006, p. 4).
  33. 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.
  34. Petzold, C. (2008). The annotated Turing: a guided tour through Alan Turing's historic paper on computability and the Turing machine. Wiley Publishing.
  35. 35.0 35.1 35.2 Basics of Automata Theory. Automata Theory.

[編輯]