自動機，狀态機，有限自動機，有限狀态機，有限狀态自動機，非确定下有限狀态自動，确定性有限狀态自動機的差別于聯系

這幾個概念暈了幾天了，搞明白了就來備注一下

FSM（Finite State Machine）

FAM（Finite Automata Machine）

DFA（Determinate Finite Automata）

NFA（Non-Determinate Finite Automat）

自動機：自動機是有限狀态機(FSM)的數學模型。

狀态機：我們現在所說的狀态機一般是有限狀态機（FSM）的簡稱。

有限自動機：

有限狀态機：

對有限狀态機的定義：有限狀态機是具有一個基本内部記憶的抽象機器模型，定義如下：

根據輸出與輸入、系統狀态的關系，有限狀态機又可分為Moore型有限狀态機和Mealy型有限狀态機

Moore型有限狀态機是指輸出僅與系統狀态有關，與輸入信号無關的狀态機。優點是将輸入和輸出分隔開.

Mealy型有限狀态機是指輸出與系統狀态和輸入均有關系的有限狀态機。

為了直覺，直接用轉移圖來說明兩者的差別

轉移圖是一種有向圖，由圓表示有限狀态機的狀态，有向曲線表示系統的狀态轉移過程，有向線段的起點 表示初始的狀态，終點表示轉移後的狀态。

對于Mealy型有限狀态機在有向曲線段上的字元表示系統的輸入和輸出，用“/”分隔。

         對于Moore型有限狀态機，通常在狀态後标出輸出值，用“/”分隔，輸入信号仍然在有向線段上标注。

圖1：Mealy型狀态機的轉移圖

圖1所示的有限狀态機隻有一位輸入、一位輸出，兩個狀态A1和A2，左側繪制的指向A1的箭頭表示系統的初始狀态為A1；在A1的上方，繪制一個起點和終點都在A1上的有向曲線，以及曲線上的标注“1/0”表示，當狀态為A1，輸入信号為1時，有限狀态機的狀态不變，輸出為0；由A1指向A2的标注為“0/1”的箭頭表示，當系統狀态為A1，輸入為0時，系統狀态變為A2，且輸出為1。同理，由轉移圖可知，當系統處于A2狀态時，輸入為1時狀态不變，輸出為1；當輸入為0時，狀态變為A1，輸出為0。對于比較複雜的有限狀态機，在有向箭頭的辨別上還可以添加字元說明。

圖2： Moore型狀态機轉移圖

圖2所示的Moore型有限狀态機隻有一位輸入、一位輸出，兩個狀态A1和A2，左側繪制的指向A1的箭頭表示系統的初始狀态為A1；标注“A1/1”表示處于狀态A1時，輸出為1；同理“A2/0”表示處于狀态A2時，系統輸出為0；在狀态A1上方繪制的起點和終點均在A1上的有向曲線，以及曲線上的标注“1”表示，當狀态為A1，輸入信号為1時，有限狀态機的狀态不變；由A1指向A2的标注為“0”的箭頭表示，當狀态為A1，輸入為0時，有限狀态機的狀态變為A2。當有限狀态機處于A2狀态時，如果輸入為1，有限狀态機的狀态就會變為A1。 

對于這種輸出在{0，1}二值區間的Moore型有限狀态機，一般稱之為有限狀态自動機，對于有限狀态自動機還有另一種轉移圖的表示方法，即用雙圓環表示輸出為1的狀态，并稱之為接受狀态。使用這種轉移圖畫法後，圖2所示的有限狀态機可繪制為如圖3所示的轉移圖。

圖3：有限狀态自動機

有限狀态自動機：（FSM "finite state machine" 或者FSA "finite state automaton" ）是為研究有限記憶體的計算過程和某些語言類而抽象出的一種計算模型。有限狀态自動機擁有有限數量的狀态，每個狀态可以遷移到零個或多個狀态，輸入字串決定執行哪個狀态的遷移。有限狀态自動機可以表示為一個有向圖。有限狀态自動機是​​自動機理論​​的研究對象。

有限狀态自動機是具有離散輸入和輸出的系統的一種數學模型

。

其主要特點有以下幾個方面：

–

(1)

系統具有有限個狀态，不同的狀态代表不同的意義。按照實際的需要，系統可以在不同的狀态下完成規定的任務。

–

(2)

我們可以将輸入字元串中出現的字元彙集在一起構成一個字母表。系統處理的所有字元串都是這個字母表上的字元串。

–

(3)

系統在任何一個狀态下，從輸入字元串中讀入一個字元，根據目前狀态和讀入的這個字元轉到新的狀态。

–

(4)

系統中有一個狀态，它是系統的開始狀态。

–

(5)

系統中還有一些狀态表示它到目前為止所讀入的字元構成的字元串是語言的一個句子。

形式定義

· 定義：有限狀态自動機(FA—finite automaton)是一個五元組：

– M=(Q, Σ, δ, q0, F)

· 其中，

– Q——狀态的非空有窮集合。∀q∈Q，q稱為M的一個狀态。

– Σ——輸入字母表。

– δ——狀态轉移函數，有時又叫作狀态

​​轉換函數​​或者移動函數，δ：Q×Σ→Q，δ(q,a)=p。

– q0——M的開始狀态，也可叫作初始狀态或啟動狀态。q0∈Q。

– F——M的終止狀态集合。F被Q包含。任給q∈F，q稱為M的終止狀态。

有限狀态自動機還可以分成确定與非确定兩種。非确定有限狀态自動機可以轉化為确定有限狀态自動機。

自動機從初始狀态 q0 起，逐一讀入輸入串（由輸入字母表 Σ 的字母構成）的每一個字母，根據目前狀态、輸入字母和轉移函數 δ 決定自動機的下一步狀态；如果輸入串結束時，自動機處于終結狀态集合 F 的某一個狀态，這表示自動機接受該字串；否則自動機不接受該字串。

非确定有限狀态自動機與确定有限狀态自動機的唯一差別是它們的轉移函數不同。确定有限狀态自動機對每一個可能的輸入隻有一個狀态的轉移。非确定有限狀态自動機對每一個可能的輸入可以有多個狀态轉移，接受到輸入時從這多個狀态轉移​​中非​​确定地選擇一個。

确定型有限狀态自動機：

形式化定義：

确定有限狀态自動機 ​​

​​是由

• 一個非空有限​​狀态​​的集合 Q
• 一個輸入字母表 Σ（非空有限字元的集合）
• 一個轉移​​函數​​​​

  

  ​​​（例如：​​

  

  ​​），每一個轉移都有确定的值
• 一個開始狀态​​

  

  ​​
• 一個接受狀态的集合​​

  

  ​​

所組成的5-​​元組​​​。是以一個DFA可以寫成這樣的形式：​​

​​ 。

非确定型有限狀态自動機：

形式化定義：

不确定有限狀态自動機 ​​

​​是由

• 一個非空有限​​狀态​​的集合 Q
• 一個輸入字母表 Σ（非空有限字元的集合）
• 一個轉移​​函數​​​​

  

  ​​ ，每一個轉移（一個狀态下，同一個輸入）都幾個不确定的值（次态），采取随機轉移方式轉移到下一個狀态
• 一個開始狀态​​

  

  ​​
• 一個接受狀态的集合​​

  

  ​​

所組成的5-​​元組​​​。是以一個DFA可以寫成這樣的形式：​​

​​ 。

DFA與NFA的不同就是轉移函數的不同。

DFA與NFA可以互相裝換，具體如何轉換參考：​​NFA轉換為DFA​​

總結：我們平常說的狀态機其實就是指有限狀态自動機，有限自動機是一套自動機理論，當被用于特定的領域之後就被稱為有限狀态機，而有限狀态機的數學模型就是自動機。

狀态機是是一個概念，一個工具。我們經常采用狀态機來對事物模組化，使用狀态機來模組化的主要學科有：

在計算機科學中自動機用作計算機和計算過程的動态數學模型，用來研究計算機的體系結構、邏輯操作、程式設計乃至計算複雜性理論。

具體應用方面：

數字電路設計

遊戲開發

單片機開發

設計模式之狀态機模式

狀态機工作流（基于事件轉移）

任何一個具有狀态變化的對象或事物都可以用狀态機來模組化

在語言學中則把自動機作為語言識别器，用來研究各種​​形式語言​​。

在神經生理學中把自動機定義為​​神經網絡​​​的​​動态模型​​，用來研究神經生理活動和思維規律，探索人腦的機制。

在生物學中有人把自動機作為生命體的生長發育模型，研究新陳代謝和遺傳變異。在數學中則用自動機定義可計算函數，研究各種算法。

看到一句話"根本沒有輸出函數的有限狀态機叫做​​半自動機​​​或​​轉移系統​​"，那麼按照有限狀态自動機的定義沒有輸出函數難道就是半自動機嗎。

版權聲明：本文為部落客原創文章，禁止一切形式的轉載，愛程式員網你自覺點。

這幾個概念暈了幾天了，搞明白了就來備注一下

FSM（Finite State Machine）

FAM（Finite Automata Machine）

DFA（Determinate Finite Automata）

NFA（Non-Determinate Finite Automat）

自動機：自動機是有限狀态機(FSM)的數學模型。

狀态機：我們現在所說的狀态機一般是有限狀态機（FSM）的簡稱。

有限自動機：

有限狀态機：

對有限狀态機的定義：有限狀态機是具有一個基本内部記憶的抽象機器模型，定義如下：

根據輸出與輸入、系統狀态的關系，有限狀态機又可分為Moore型有限狀态機和Mealy型有限狀态機

Moore型有限狀态機是指輸出僅與系統狀态有關，與輸入信号無關的狀态機。優點是将輸入和輸出分隔開.

Mealy型有限狀态機是指輸出與系統狀态和輸入均有關系的有限狀态機。

為了直覺，直接用轉移圖來說明兩者的差別

轉移圖是一種有向圖，由圓表示有限狀态機的狀态，有向曲線表示系統的狀态轉移過程，有向線段的起點 表示初始的狀态，終點表示轉移後的狀态。

對于Mealy型有限狀态機在有向曲線段上的字元表示系統的輸入和輸出，用“/”分隔。

         對于Moore型有限狀态機，通常在狀态後标出輸出值，用“/”分隔，輸入信号仍然在有向線段上标注。

圖1：Mealy型狀态機的轉移圖

圖1所示的有限狀态機隻有一位輸入、一位輸出，兩個狀态A1和A2，左側繪制的指向A1的箭頭表示系統的初始狀态為A1；在A1的上方，繪制一個起點和終點都在A1上的有向曲線，以及曲線上的标注“1/0”表示，當狀态為A1，輸入信号為1時，有限狀态機的狀态不變，輸出為0；由A1指向A2的标注為“0/1”的箭頭表示，當系統狀态為A1，輸入為0時，系統狀态變為A2，且輸出為1。同理，由轉移圖可知，當系統處于A2狀态時，輸入為1時狀态不變，輸出為1；當輸入為0時，狀态變為A1，輸出為0。對于比較複雜的有限狀态機，在有向箭頭的辨別上還可以添加字元說明。

圖2： Moore型狀态機轉移圖

圖2所示的Moore型有限狀态機隻有一位輸入、一位輸出，兩個狀态A1和A2，左側繪制的指向A1的箭頭表示系統的初始狀态為A1；标注“A1/1”表示處于狀态A1時，輸出為1；同理“A2/0”表示處于狀态A2時，系統輸出為0；在狀态A1上方繪制的起點和終點均在A1上的有向曲線，以及曲線上的标注“1”表示，當狀态為A1，輸入信号為1時，有限狀态機的狀态不變；由A1指向A2的标注為“0”的箭頭表示，當狀态為A1，輸入為0時，有限狀态機的狀态變為A2。當有限狀态機處于A2狀态時，如果輸入為1，有限狀态機的狀态就會變為A1。 

對于這種輸出在{0，1}二值區間的Moore型有限狀态機，一般稱之為有限狀态自動機，對于有限狀态自動機還有另一種轉移圖的表示方法，即用雙圓環表示輸出為1的狀态，并稱之為接受狀态。使用這種轉移圖畫法後，圖2所示的有限狀态機可繪制為如圖3所示的轉移圖。

圖3：有限狀态自動機

有限狀态自動機：（FSM "finite state machine" 或者FSA "finite state automaton" ）是為研究有限記憶體的計算過程和某些語言類而抽象出的一種計算模型。有限狀态自動機擁有有限數量的狀态，每個狀态可以遷移到零個或多個狀态，輸入字串決定執行哪個狀态的遷移。有限狀态自動機可以表示為一個有向圖。有限狀态自動機是​​自動機理論​​的研究對象。

有限狀态自動機是具有離散輸入和輸出的系統的一種數學模型

。

其主要特點有以下幾個方面：

–

(1)

系統具有有限個狀态，不同的狀态代表不同的意義。按照實際的需要，系統可以在不同的狀态下完成規定的任務。

–

(2)

我們可以将輸入字元串中出現的字元彙集在一起構成一個字母表。系統處理的所有字元串都是這個字母表上的字元串。

–

(3)

系統在任何一個狀态下，從輸入字元串中讀入一個字元，根據目前狀态和讀入的這個字元轉到新的狀态。

–

(4)

系統中有一個狀态，它是系統的開始狀态。

–

(5)

系統中還有一些狀态表示它到目前為止所讀入的字元構成的字元串是語言的一個句子。

形式定義

· 定義：有限狀态自動機(FA—finite automaton)是一個五元組：

– M=(Q, Σ, δ, q0, F)

· 其中，

– Q——狀态的非空有窮集合。∀q∈Q，q稱為M的一個狀态。

– Σ——輸入字母表。

– δ——狀态轉移函數，有時又叫作狀态

​​轉換函數​​或者移動函數，δ：Q×Σ→Q，δ(q,a)=p。

– q0——M的開始狀态，也可叫作初始狀态或啟動狀态。q0∈Q。

– F——M的終止狀态集合。F被Q包含。任給q∈F，q稱為M的終止狀态。

有限狀态自動機還可以分成确定與非确定兩種。非确定有限狀态自動機可以轉化為确定有限狀态自動機。

自動機從初始狀态 q0 起，逐一讀入輸入串（由輸入字母表 Σ 的字母構成）的每一個字母，根據目前狀态、輸入字母和轉移函數 δ 決定自動機的下一步狀态；如果輸入串結束時，自動機處于終結狀态集合 F 的某一個狀态，這表示自動機接受該字串；否則自動機不接受該字串。

非确定有限狀态自動機與确定有限狀态自動機的唯一差別是它們的轉移函數不同。确定有限狀态自動機對每一個可能的輸入隻有一個狀态的轉移。非确定有限狀态自動機對每一個可能的輸入可以有多個狀态轉移，接受到輸入時從這多個狀态轉移​​中非​​确定地選擇一個。

确定型有限狀态自動機：

形式化定義：

确定有限狀态自動機 ​​

​​是由

• 一個非空有限​​狀态​​的集合 Q
• 一個輸入字母表 Σ（非空有限字元的集合）
• 一個轉移​​函數​​​​

  

  ​​​（例如：​​

  

  ​​），每一個轉移都有确定的值
• 一個開始狀态​​

  

  ​​
• 一個接受狀态的集合​​

  

  ​​

所組成的5-​​元組​​​。是以一個DFA可以寫成這樣的形式：​​

​​ 。

非确定型有限狀态自動機：

形式化定義：

不确定有限狀态自動機 ​​

​​是由

• 一個非空有限​​狀态​​的集合 Q
• 一個輸入字母表 Σ（非空有限字元的集合）
• 一個轉移​​函數​​​​

  

  ​​ ，每一個轉移（一個狀态下，同一個輸入）都幾個不确定的值（次态），采取随機轉移方式轉移到下一個狀态
• 一個開始狀态​​

  

  ​​
• 一個接受狀态的集合​​

  

  ​​

所組成的5-​​元組​​​。是以一個DFA可以寫成這樣的形式：​​

​​ 。

DFA與NFA的不同就是轉移函數的不同。

DFA與NFA可以互相裝換，具體如何轉換參考：​​NFA轉換為DFA​​

總結：我們平常說的狀态機其實就是指有限狀态自動機，有限自動機是一套自動機理論，當被用于特定的領域之後就被稱為有限狀态機，而有限狀态機的數學模型就是自動機。

狀态機是是一個概念，一個工具。我們經常采用狀态機來對事物模組化，使用狀态機來模組化的主要學科有：

在計算機科學中自動機用作計算機和計算過程的動态數學模型，用來研究計算機的體系結構、邏輯操作、程式設計乃至計算複雜性理論。

具體應用方面：

數字電路設計

遊戲開發

單片機開發

設計模式之狀态機模式

狀态機工作流（基于事件轉移）

任何一個具有狀态變化的對象或事物都可以用狀态機來模組化

在語言學中則把自動機作為語言識别器，用來研究各種​​形式語言​​。

在神經生理學中把自動機定義為​​神經網絡​​​的​​動态模型​​，用來研究神經生理活動和思維規律，探索人腦的機制。

在生物學中有人把自動機作為生命體的生長發育模型，研究新陳代謝和遺傳變異。在數學中則用自動機定義可計算函數，研究各種算法。