Scientific FigureScientific Figure
DFA、NFA、Moore、Mealy 和 UML

免費狀態圖產生器,畫有限狀態機 FSM、DFA 與 UML 狀態機圖

免費的狀態圖產生器,適合計算理論課、數位邏輯和軟體設計。每行輸入一條轉移,就會自動排好有限狀態機或 UML 狀態機圖,附起始箭頭、接受狀態雙圈、自迴圈和狀態轉移表。

標題
轉移,每行一條

轉移寫成 q0 -a-> q1、q0 -> q1 : a,或三欄試算表。再加上 start: 和 accept: 兩行;走同一個箭頭的輸入會合併成「0, 1」。如果沒有 start: 行指定別的狀態,狀態圖產生器就把第一個狀態當作起始狀態。

3 個狀態,6 條轉移,輸入字母集 {0, 1}。每個狀態對每個符號都剛好有一條轉移,所以這是一個完整的 DFA。

方向
顏色
下載

狀態圖產生器就在這個瀏覽器分頁裡排版:不需要帳號,不會上傳資料,檔案歸你所有。

辨識以 01 結尾之二進位字串的 DFA(狀態圖)q0 讀入 0 時轉到 q1; q1 讀入 1 時轉到 q2; q2 讀入 0 時轉到 q1; q2 讀入 1 時轉到 q0; q0 讀入 1 時轉到 q0; q1 讀入 0 時轉到 q1辨識以 01 結尾之二進位字串的 DFA開始010110q0q1q2scientificfigure.com
想要手繪白板版本、放進投影片的插畫版紅綠燈或自動販賣機,還是設計文件用的配圖?
狀態轉移表→ 起始狀態,* 接受狀態
狀態輸入 0輸入 1
→ q0q1q0
q1q1q2
* q2q1q0

狀態圖範例

狀態圖產生器的 AI 產生器畫的八個狀態圖範例:自動販賣機、TCP 連線狀態、一個 DFA、一條馬可夫鏈,以及四種風格。每張都是實際繪製的成品,並附上畫出它的提示詞;點一張卡片就能載入提示詞。

自動販賣機

自動販賣機的 UML 狀態機圖,每個箭頭都寫著 觸發事件 [防護條件] / 效果,由狀態圖產生器的 AI 部分繪製。

TCP 連線

依 RFC 9293 畫的 TCP 連線狀態圖,由狀態圖產生器繪製:從 CLOSED 到 TIME-WAIT 共十一個狀態,寫出每個事件和動作。

能被 3 整除的 DFA

接受能被 3 整除的二進位數的 DFA,附起始箭頭和接受狀態雙圈,由狀態圖產生器繪製。

天氣的馬可夫鏈

每日天氣的馬可夫鏈,每個箭頭上寫著轉移機率,出自狀態圖產生器的 AI 產生器。

偵測 101 的 Moore 機

狀態圖產生器裡 AI 產生器畫的課本插圖:輸入 101 後輸出 1 的 Moore 機,輸出寫在狀態裡面。

行人穿越道號誌

狀態圖產生器裡 AI 產生器畫的白板草圖:有計時轉移和按鈕觸發的行人穿越道號誌,用麥克筆畫成。

網購訂單生命週期

狀態圖產生器的插畫風格:網購訂單狀態機圖,每個狀態配一個小圖示,從待付款到已送達或已退款。

電梯控制器

狀態圖產生器的深色投影片:轉移上有防護條件的電梯控制器,可以直接拿來演講或上課。

什麼是狀態圖?

狀態圖畫的是一個系統可能處於的各個狀態,以及它們之間的轉移:每個狀態是一個節點,每個箭頭是一條轉移,箭頭上標著引起轉移的輸入或事件。 同一種圖也叫狀態轉移圖、狀態機圖(UML 的名稱)或狀態圖表(statechart),後者得名於 David Harel 的擴充形式,UML 的狀態機就是以它為基礎。

狀態圖產生器能做什麼

  • 狀態圖產生器每行讀一條轉移:上課筆記裡的 q0 -a-> q1、Mermaid 的 A --> B : 事件,或三欄試算表都可以。
  • 自動機表示法:一個不從任何狀態出發的箭頭指向起始狀態,接受狀態畫成雙圈,支援自迴圈,共用一個箭頭的輸入合併成「0, 1」。
  • UML 表示法:圓角矩形表示狀態,實心小圓表示初始虛擬狀態,實心圓點外加一圈表示終止狀態,箭頭標註為 觸發事件 [防護條件] / 效果。
  • 狀態圖產生器在繪製前會檢查每一種版面:任兩個狀態都不重疊,標註不會壓在狀態、其他標註或其他箭頭上。
  • 狀態轉移表出自同一份清單:DFA 每個狀態一列,NFA 填下一個狀態的集合,Mealy 機填 下一個狀態 / 輸出,馬可夫鏈則給出轉移矩陣。
  • 狀態圖產生器的狀態列會說明這是 DFA 還是 NFA,列出缺少的轉移和到不了的狀態,並檢查馬可夫鏈的機率和是否為 1。
  • 狀態圖產生器可下載彩色或黑白的 PNG、SVG 和 PDF 檔,免費且不必登入。

UML 和自動機理論中的狀態圖表示法

有兩套慣例都叫狀態圖,一張狀態圖應該從頭到尾只用其中一套。 軟體設計用 UML 狀態機,狀態是圓角矩形,箭頭上寫 觸發事件 [防護條件] / 效果。計算理論和數位邏輯課把狀態畫成圓圈,用一個不從任何狀態出發的箭頭標出起始狀態,用雙圈標出接受狀態。狀態圖產生器能用同一份轉移清單畫出任一種。

有限狀態機(自動機)
符號名稱意義
起始狀態有一個不從任何狀態出發的箭頭指向它,箭頭常標 start。DFA 剛好有一個起始狀態。
狀態一個寫著狀態名稱(例如 q0)的圓圈。Moore 機把輸出寫在斜線後面,如 S3/1。
接受狀態(終止狀態)在圓圈裡再套一個圓圈。一台狀態機可以有好幾個接受狀態,也可以一個都沒有。
自迴圈離開一個狀態又回到它自己的轉移,標上對應的輸入。
0, 1轉移標註走這個箭頭的輸入符號,用逗號分隔;ε 表示不讀輸入的轉移,只有 NFA 才能有。
1/0Mealy 輸出箭頭上寫 輸入/輸出,例如 1/0:輸出屬於轉移,而不屬於狀態。
自動機表示法:起始狀態「偶」同時也是接受狀態,所以它既有起始箭頭,又畫成雙圈。狀態圖產生器用六行轉移排出這張圖。偶 讀入 0 時轉到 奇; 奇 讀入 0 時轉到 偶; 偶 讀入 1 時轉到 偶; 奇 讀入 1 時轉到 奇辨識含偶數個 0 之字串的 DFA開始0011偶奇
自動機表示法:起始狀態「偶」同時也是接受狀態,所以它既有起始箭頭,又畫成雙圈。狀態圖產生器用六行轉移排出這張圖。
UML 狀態機(UML 2.5.1)
符號名稱意義
初始虛擬狀態一個實心小圓。從它出發的唯一一條轉移沒有觸發事件,也沒有防護條件。
狀態寫著狀態名稱的圓角矩形;可加一個區隔列出 entry /、do / 和 exit / 行為。
e [g] / a轉移觸發事件 [防護條件] / 效果,每一部分都可以省略:投幣 / 解鎖,選擇商品 [餘額 ≥ 價格] / 出貨。
終止狀態一個實心小圓外加一圈:這個區域已經完成。
選擇虛擬狀態一個菱形,從它出發的轉移帶有決定走哪條分支的防護條件。
UML 表示法:初始虛擬狀態指向「上鎖」,兩個狀態都有自迴圈,「關機」通往終止狀態。這些行是以 Mermaid 格式貼進狀態圖產生器的。上鎖 讀入 投幣 / 解鎖 時轉到 開鎖; 開鎖 讀入 推 / 鎖上 時轉到 上鎖; 上鎖 讀入 關機 時轉到 ; 上鎖 讀入 推 / 警報 時轉到 上鎖; 開鎖 讀入 投幣 / 致謝 時轉到 開鎖投幣式閘門投幣 / 解鎖推 / 鎖上關機推 / 警報投幣 / 致謝上鎖開鎖
UML 表示法:初始虛擬狀態指向「上鎖」,兩個狀態都有自迴圈,「關機」通往終止狀態。這些行是以 Mermaid 格式貼進狀態圖產生器的。

怎麼讀狀態轉移表

狀態轉移表就是寫成表格的狀態圖:每個狀態一列,每個輸入一欄,每一格是狀態機轉到的狀態。 箭頭 → 標出起始狀態,* 標出接受狀態。表和圖包含同樣的資訊,所以考試常要你由其中一個畫出另一個;狀態圖產生器會在每張圖下面產生這張表。

狀態圖產生器畫的能被 3 整除之二進位數 DFA。狀態 ri 表示到目前為止讀到的位元構成的數除以 3 餘 i。r0 讀入 1 時轉到 r1; r1 讀入 0 時轉到 r2; r1 讀入 1 時轉到 r0; r2 讀入 0 時轉到 r1; r0 讀入 0 時轉到 r0; r2 讀入 1 時轉到 r2辨識能被 3 整除之二進位數的 DFA開始101001r0r1r2
狀態圖產生器畫的能被 3 整除之二進位數 DFA。狀態 ri 表示到目前為止讀到的位元構成的數除以 3 餘 i。
狀態輸入 0輸入 1
→ * r0r0r1
r1r2r0
r2r1r2
  • 一列讀作「從這個狀態出發,讀入這個輸入,轉到」:r1 讀入 0 轉到 r2,因為目前讀到的數乘以 2 之後餘 2。
  • DFA 的每一格剛好有一個狀態。狀態圖產生器把缺少的轉移顯示成空格(—):這個 DFA 是部分的,課本會加一個死狀態把它補完整。
  • 在 NFA 裡,一格可以是一個狀態集合 {q0, q1} 或 ∅,ε 欄列出不消耗輸入的轉移。
  • Mealy 機的表在每格寫 下一個狀態 / 輸出;馬可夫鏈的表是轉移矩陣,每一列的和為 1。

Moore 機和 Mealy 機的狀態圖

Moore 機的輸出只取決於目前的狀態,所以輸出寫在狀態裡;Mealy 機的輸出取決於狀態和輸入,所以寫在箭頭上,形式為 輸入/輸出。 下面兩張圖都偵測可重疊的序列 101。Mealy 版只要三個狀態,Moore 版要四個,因為 Moore 機需要單獨一個狀態表示「剛讀到 101」。狀態圖產生器分別用九行和七行轉移畫出它們。

狀態圖產生器裡的 Moore 機:S3/1 是唯一輸出 1 的狀態。S0/0 讀入 1 時轉到 S1/0; S1/0 讀入 0 時轉到 S2/0; S2/0 讀入 1 時轉到 S3/1; S3/1 讀入 0 時轉到 S2/0; S2/0 讀入 0 時轉到 S0/0; S3/1 讀入 1 時轉到 S1/0; S0/0 讀入 0 時轉到 S0/0; S1/0 讀入 1 時轉到 S1/0偵測 101 的 Moore 機(可重疊)開始10100101S0/0S1/0S2/0S3/1
狀態圖產生器裡的 Moore 機:S3/1 是唯一輸出 1 的狀態。
狀態圖產生器裡的 Mealy 機:標註為 1/1 的箭頭 S2 → S1 是唯一輸出 1 的轉移。S0 讀入 1/0 時轉到 S1; S1 讀入 0/0 時轉到 S2; S2 讀入 1/1 時轉到 S1; S2 讀入 0/0 時轉到 S0; S0 讀入 0/0 時轉到 S0; S1 讀入 1/0 時轉到 S1偵測 101 的 Mealy 機(可重疊)開始1/00/01/10/00/01/0S0S1S2
狀態圖產生器裡的 Mealy 機:標註為 1/1 的箭頭 S2 → S1 是唯一輸出 1 的轉移。
Moore 機Mealy 機
輸出取決於只看目前的狀態目前的狀態和輸入
輸出寫在哪裡狀態裡:S3/1轉移上:1/1
偵測 101 所需狀態數43
輸出何時改變只在進入新狀態時輸入一變就變
在狀態轉移表裡每列一個輸出,寫在狀態旁每格寫 下一個狀態 / 輸出

學生和工程師常畫的狀態圖

每張卡片都會在上面的狀態圖產生器裡開啟一張現成的狀態轉移圖,已經排好版並附上表格,可以修改或下載。

TCP 連線狀態圖

現行 TCP 標準 RFC 9293 用圖 5 概括一條連線:從 CLOSED 經 LISTEN、SYN-SENT、ESTAB 到 TIME-WAIT 共十一個狀態,每個箭頭都標出事件和它觸發的動作。RFC 本身也提醒,這張圖「只是摘要,不能當成完整的規格」。這裡的圖是狀態圖產生器依原圖中的二十條轉移畫出來的,和原圖一樣由上到下排列。

依 RFC 9293 圖 5 畫的 TCP 連線狀態圖,由狀態圖產生器繪製。CLOSE-WAIT 讀入 CLOSE / snd FIN 時轉到 LAST-ACK; SYN-RCVD 讀入 CLOSE / snd FIN 時轉到 FIN-WAIT-1; LISTEN 讀入 rcv SYN / snd SYN,ACK 時轉到 SYN-RCVD; SYN-RCVD 讀入 rcv RST 時轉到 LISTEN; SYN-SENT 讀入 rcv SYN,ACK / snd ACK 時轉到 ESTAB; FIN-WAIT-1 讀入 rcv ACK of FIN 時轉到 FIN-WAIT-2; FIN-WAIT-1 讀入 rcv FIN / snd ACK 時轉到 CLOSING; FIN-WAIT-2 讀入 rcv FIN / snd ACK 時轉到 TIME-WAIT; CLOSING 讀入 rcv ACK of FIN 時轉到 TIME-WAIT; ESTAB 讀入 rcv FIN / snd ACK 時轉到 CLOSE-WAIT; CLOSED 讀入 passive OPEN / create TCB 時轉到 LISTEN; CLOSED 讀入 active OPEN / create TCB, snd SYN 時轉到 SYN-SENT; LISTEN 讀入 CLOSE / delete TCB 時轉到 CLOSED; SYN-SENT 讀入 CLOSE / delete TCB 時轉到 CLOSED; SYN-SENT 讀入 rcv SYN / snd SYN,ACK 時轉到 SYN-RCVD; ESTAB 讀入 CLOSE / snd FIN 時轉到 FIN-WAIT-1; LISTEN 讀入 SEND / snd SYN 時轉到 SYN-SENT; SYN-RCVD 讀入 rcv ACK of SYN 時轉到 ESTAB; LAST-ACK 讀入 rcv ACK of FIN 時轉到 CLOSED; TIME-WAIT 讀入 Timeout=2MSL / delete TCB 時轉到 CLOSEDTCP 連線狀態圖(RFC 9293,圖 5)CLOSE / snd FINCLOSE / snd FINrcv SYN/ snd SYN,ACKrcv RSTrcv SYN,ACK/ snd ACKrcv ACK of FINrcv FIN / snd ACKrcv FIN / snd ACKrcv ACK of FINrcv FIN / snd ACKpassive OPEN/ create TCBactive OPEN/ create TCB, sndSYNCLOSE/ delete TCBCLOSE/ delete TCBrcv SYN/ snd SYN,ACKCLOSE / snd FINSEND / snd SYNrcv ACK of SYNrcv ACK of FINTimeout=2MSL/ delete TCBCLOSEDLISTENSYN-SENTSYN-RCVDESTABFIN-WAIT-1CLOSE-WAITFIN-WAIT-2CLOSINGTIME-WAITLAST-ACK
依 RFC 9293 圖 5 畫的 TCP 連線狀態圖,由狀態圖產生器繪製。

DFA 狀態圖

DFA 是最簡單的有限狀態機,計算理論課的習題常要畫一個接受某種語言的 DFA,例如能被 3 整除的二進位數。三個狀態記錄餘數,r0 既是起始狀態也是接受狀態,每個狀態對 0 和 1 各有一個箭頭。

含 ε 轉移的 NFA 狀態圖

NFA 對同一個符號可以有好幾個箭頭,也可以有標 ε 的箭頭。這個 NFA 接受 a* ∪ b*:從 q0 出發的兩條 ε 轉移選擇分支,q1 和 q2 都是接受狀態。

JK 正反器狀態圖

兩個狀態 Q=0 和 Q=1。從 Q=0 出發,輸入 JK = 0X 讓 Q 保持 0,1X 設定為 1;從 Q=1 出發,X0 保持,X1 重置。X 表示隨意項(don't care),所以四種輸入組合在每個狀態各用兩個箭頭就能畫完。

在電路圖產生器裡畫出正反器電路本身

計數器狀態圖

2 位元上數/下數計數器在 00、01、10、11 之間循環:輸入 1 往前一步,輸入 0 往後一步,所以每對相鄰狀態之間都有兩個箭頭。

紅綠燈狀態圖

用 UML 表示法畫的計時控制器:30 s 後紅燈轉綠燈,25 s 後綠燈轉黃燈,5 s 後黃燈轉紅燈。after 是 UML 表示時間事件的關鍵字。

自動販賣機狀態圖

經典的軟體設計練習:閒置、收幣中、出貨中三個狀態,選擇商品的箭頭上有防護條件 [餘額 ≥ 價格],斜線後面寫動作。

訂單生命週期狀態機

商業物件也有狀態。訂單從待付款到已付款、已出貨、已送達,或以已取消、已退款結束;每個結束狀態都指向 UML 終止狀態。

馬可夫鏈狀態圖

在馬可夫鏈裡,每個箭頭都帶一個機率,離開同一狀態的箭頭機率和為 1。表格變成轉移矩陣,任何一列的和不是 1,狀態圖產生器都會標出來。

用機率樹狀圖追蹤兩步變化

怎麼畫狀態圖

  1. 1

    列出狀態和起點

    在狀態圖產生器輸入之前,先寫出系統可能停留的每一種狀態。在自動機表示法裡其中一個是起始狀態;在 UML 裡狀態機從初始虛擬狀態開始。

  2. 2

    把轉移輸入狀態圖產生器

    每條轉移一行:離開的狀態、輸入或事件、進入的狀態。狀態轉移圖會隨輸入即時重畫,回到同一狀態的轉移會變成自迴圈。

  3. 3

    標出接受狀態或終止狀態

    自動機加一行 accept: q2,UML 終止狀態寫 狀態 --> [*]。狀態圖產生器的狀態列會指出缺少的轉移和到不了的狀態。

  4. 4

    核對表格,再從狀態圖產生器下載

    拿狀態轉移表和你的答案對照,需要時改成由上到下或黑白,再從狀態圖產生器儲存成 PNG、SVG 或 PDF。

狀態圖產生器常見問題

狀態圖和狀態機圖有什麼不同?

+

它們是同一種圖;狀態機圖是 UML 用的名稱。 狀態圖和狀態轉移圖是通用說法,用在自動機理論和數位邏輯。狀態圖表(statechart)是 David Harel 加入巢狀狀態和平行狀態的擴充,UML 2.5.1 規格說明它的狀態機以 Harel 狀態圖表的一種物件導向變體為基礎。狀態圖產生器用兩種表示法都能畫一般的狀態機,但不畫巢狀狀態。

怎麼標出起始狀態和接受狀態?

+

在狀態圖產生器裡加一行 start: 和一行 accept:,例如 start: q0 和 accept: q2, q3。 起始狀態會有一個不從任何狀態出發的箭頭,每個接受狀態畫成雙圈。沒有 start: 行時,你寫的第一個狀態就是起始狀態。在 UML 表示法裡,初始轉移寫 [*] --> 狀態,指向終止狀態的轉移寫 狀態 --> [*]。

怎麼從狀態圖分辨 DFA 和 NFA?

+

DFA 狀態圖裡每個狀態對每個輸入符號都剛好有一個離開的箭頭,而且沒有 ε 標註;不符合這些的就是 NFA。 NFA 對同一符號可以有兩個箭頭,也可以一個都沒有,還可以有 ε 轉移。狀態圖產生器的狀態列會告訴你畫的是哪一種,並指出造成不確定性的狀態和符號,或部分 DFA 缺少的轉移。

怎麼把狀態圖轉成狀態轉移表?

+

每個狀態寫一列,每個輸入符號寫一欄,每格填下一個狀態;狀態圖產生器會在圖下面產生這張表。 用 → 標起始狀態,用 * 標接受狀態。NFA 的每格是一個狀態集合,Mealy 機的每格是 下一個狀態 / 輸出。這張表可以複製,或下載成 CSV。

可以貼上 Mermaid 或 PlantUML 的狀態圖程式碼嗎?

+

可以:[*] --> Idle、Idle --> Running : start 和 Running --> [*] 這類轉移行,可以原封不動貼進狀態圖產生器。 stateDiagram-v2 標頭、@startuml、註解和方向行會被略過。用 state X { … } 寫的複合狀態不會畫出;請把它內部的轉移寫成一般的行。

狀態圖和流程圖是一樣的嗎?

+

不一樣。流程圖依先後順序排出一個程序的各個步驟;狀態圖呈現系統停留的各種狀態,以及讓它在狀態之間切換的事件。 閘門是一台狀態機,因為同樣推一下,上鎖時和開鎖時結果不同。在 UML 裡,和流程圖相對應的是活動圖。狀態圖產生器裡的閘門範例正好說明兩者的差別。

JK 正反器的狀態圖長什麼樣子?

+

兩個狀態 Q=0 和 Q=1,四個箭頭:0X 讓 Q 保持 0,1X 設定為 1,X0 保持 1,X1 重置為 0。 X 表示隨意項,所以 J = 1、K = 1(反轉)已經被 Q=0 出發的 1X 和 Q=1 出發的 X1 涵蓋。狀態圖產生器裡的 JK 正反器範例會連同狀態轉移表一起畫出來。

怎麼畫馬可夫鏈狀態圖?

+

在狀態圖產生器裡替每個箭頭標上轉移機率,例如 晴 -0.7-> 晴,停在原狀態的機率畫成自迴圈。 當每個標註都是機率時,狀態圖產生器會把清單當作馬可夫鏈來讀:表格變成轉移矩陣,任何一個出發機率和不是 1 的狀態都會被標出。

狀態圖產生器最多能畫多大的狀態機?

+

狀態圖產生器最多畫 16 個狀態和 48 條轉移。 每種版面在顯示前都會檢查,如果一台狀態機不讓標註相碰就畫不出來,狀態圖產生器會直接說明,而不是畫成一團亂:可以在由左到右和由上到下之間切換、縮短標註,或把狀態機拆成幾部分。

AI 產生器能畫插畫風或手繪風的狀態圖嗎?

+

可以。狀態圖產生器旁邊的 AI 產生器能畫課本、白板、插畫和深色投影片四種版本,也能把畫在紙上的狀態圖照片重新畫好。 從免費狀態圖產生器傳過來的轉移,會以精確的狀態和箭頭清單交給模型,所以它照著你的狀態機畫,而不是自己編一個。每個新帳號贈送 100 點免費點數。

在狀態圖產生器裡畫出來

輸入轉移,核對表格,下載成圖。狀態圖產生器免費使用,不需要帳號。

開啟狀態圖產生器