Scientific FigureScientific Figure
DFA・NFA・ムーア・ミーリ・UML

状態遷移図 作成ツール ステートマシン図と有限オートマトン

オートマトンの授業、論理回路、ソフトウェア設計のための無料の状態遷移図 作成ツールです。1 行に 1 つ遷移を書くだけで、有限オートマトンや UML のステートマシン図が自動で配置され、開始の矢印、受理状態の二重丸、自己ループ、状態遷移表まで描かれます。

タイトル
遷移(1 行に 1 つ)

遷移は q0 -a-> q1、q0 -> q1 : a、またはスプレッドシートの 3 列で書きます。start: と accept: の行を加えます。同じ矢印をたどる入力は "0, 1" のようにまとめます。start: の行で別の状態を指定しない限り、状態遷移図 作成ツールは最初の状態を開始状態とみなします。

3 状態、6 遷移、入力アルファベット {0, 1}。どの状態も各記号でちょうど 1 つの遷移をもつので、完全な DFA です。

向き
色
ダウンロード

状態遷移図 作成ツールはこのブラウザのタブ内でマシンを配置します。アカウントもアップロードも不要で、ファイルは自由に使えます。

01 で終わる 2 進文字列の DFA(状態遷移図)q0 は 0 で q1 へ遷移; q1 は 1 で q2 へ遷移; q2 は 0 で q1 へ遷移; q2 は 1 で q0 へ遷移; q0 は 1 で q0 へ遷移; q1 は 0 で q1 へ遷移01 で終わる 2 進文字列の DFAstart010110q0q1q2scientificfigure.com
ホワイトボードの手描き版、スライド用のイラスト入り信号機や自動販売機、設計書用の図にしたいですか?
状態遷移表→ 開始状態、* 受理状態
状態入力 0入力 1
→ q0q1q0
q1q1q2
* q2q1q0

状態遷移図の例

状態遷移図 作成ツールの AI ジェネレーターで描いた状態遷移図の例を 8 つ紹介します。自動販売機、TCP コネクションの状態、DFA、マルコフ連鎖と、4 つの仕上がりです。どれも実際に描いた画像で、描いたプロンプトが付いています。カードを選ぶとプロンプトを読み込みます。

自動販売機

どの矢印にもトリガー [ガード] / エフェクトを書いた自動販売機の UML ステートマシン図。状態遷移図 作成ツールの AI 側で作成。

TCP コネクション

RFC 9293 に基づく TCP コネクションの状態遷移図を状態遷移図 作成ツールで描画。CLOSED から TIME-WAIT までの 11 状態と、すべてのイベントとアクション。

3 で割り切れる DFA

3 で割り切れる 2 進数を受理する DFA。開始の矢印と受理状態の二重丸付きで、状態遷移図 作成ツールが描画。

天気のマルコフ連鎖

どの矢印にも遷移確率を書いた毎日の天気のマルコフ連鎖。状態遷移図 作成ツールの AI ジェネレーターで作成。

101 を検出するムーアマシン

状態遷移図 作成ツールの AI ジェネレーターによる教科書の図。入力 101 のあとに 1 を出すムーアマシンで、出力は状態の中に書く。

押しボタン式の歩行者信号

状態遷移図 作成ツールの AI ジェネレーターによるホワイトボードの手描き。時間による遷移とボタン押下のある歩行者信号をマーカーで。

ネット注文のライフサイクル

状態遷移図 作成ツールのイラスト入り仕上げ。注文受付から配達済みか返金済みまで、各状態に小さなアイコンを入れたネット注文のステートマシン図。

エレベーター制御

状態遷移図 作成ツールのダークスライド。遷移にガード条件の付いたエレベーター制御で、発表や講義にそのまま使える。

状態遷移図とは?

状態遷移図とは、システムがとりうる状態と、その間の遷移を描いた図です。状態はノード、矢印は遷移で、遷移を引き起こす入力やイベントをラベルとして書きます。 同じ図は、状態図、ステートマシン図(UML での呼び名)、ステートチャートとも呼ばれます。ステートチャートは David Harel の拡張形式の名前で、UML のステートマシンはこれに基づいています。

状態遷移図 作成ツールでできること

  • 状態遷移図 作成ツールは 1 行に 1 つの遷移を読み取ります。授業ノートの q0 -a-> q1、Mermaid の A --> B : event、スプレッドシートの 3 列のどれでもかまいません。
  • オートマトンの記法:何もないところから開始状態への矢印、受理状態の二重丸、自己ループ、同じ矢印をたどる入力は "0, 1" のようにまとめて表示。
  • UML の記法:角の丸い四角形の状態、開始擬似状態の小さな黒丸、終了状態の黒丸を囲む輪、トリガー [ガード] / エフェクトのラベル付きの矢印。
  • 状態遷移図 作成ツールは描く前にすべての配置を確かめます。状態どうしは重ならず、ラベルが状態、ほかのラベル、ほかの矢印の上に来ることもありません。
  • 状態遷移表は同じリストから作ります。DFA なら 1 状態 1 行、NFA なら次の状態の集合、ミーリマシンなら次の状態 / 出力、マルコフ連鎖なら遷移行列です。
  • 状態遷移図 作成ツールのステータス行は、マシンが DFA か NFA かを示し、足りない遷移と到達しない状態を挙げ、マルコフ連鎖の確率の合計が 1 になるかを確かめます。
  • 状態遷移図 作成ツールは PNG、SVG、PDF をカラーか白黒で、無料、ログインなしでダウンロードできます。

UML とオートマトン理論の状態遷移図の記法

同じ名前で 2 つの流儀があり、1 枚の状態遷移図ではどちらか一方を通して使います。 ソフトウェア設計では UML のステートマシンを使い、状態は角の丸い四角形、矢印にはトリガー [ガード] / エフェクトを書きます。オートマトンや論理回路の授業では状態を円で描き、開始状態を何もないところからの矢印で、受理状態を二重丸で示します。状態遷移図 作成ツールは、同じ遷移のリストからどちらでも描けます。

有限オートマトン
記号名前意味
開始状態何もないところからの矢印が向いている状態。矢印には start と書くことが多い。DFA ではちょうど 1 つ。
状態q0 のような状態名を書いた円。ムーアマシンでは S3/1 のようにスラッシュのあとに出力を書く。
受理状態(終状態)円の内側にもう 1 つ円を描く。受理状態は複数あっても、1 つもなくてもよい。
自己ループ状態を出て同じ状態に戻る遷移。入力をラベルとして書く。
0, 1遷移のラベルその矢印をたどる入力記号をカンマで区切って書く。ε は入力なしの遷移で、NFA だけがもてる。
1/0ミーリ出力1/0 のように矢印に入力/出力を書く。出力は状態ではなく遷移に属する。
オートマトンの記法:開始状態「偶数」は受理状態でもあるので、開始の矢印と二重丸の両方が付く。状態遷移図 作成ツールが 6 行から配置した。偶数 は 0 で 奇数 へ遷移; 奇数 は 0 で 偶数 へ遷移; 偶数 は 1 で 偶数 へ遷移; 奇数 は 1 で 奇数 へ遷移0 の個数が偶数の DFAstart0011偶数奇数
オートマトンの記法:開始状態「偶数」は受理状態でもあるので、開始の矢印と二重丸の両方が付く。状態遷移図 作成ツールが 6 行から配置した。
UML ステートマシン(UML 2.5.1)
記号名前意味
開始擬似状態小さな黒丸。そこから出る 1 本の遷移にはトリガーもガードも付けない。
状態角の丸い四角形に状態名を書く。任意の区画に entry /、do /、exit / の振る舞いを書ける。
e [g] / a遷移トリガー [ガード] / エフェクト。どの部分も省略可。例:硬貨 / ロックを外す、商品選択 [残高 ≥ 価格] / 商品を出す。
終了状態小さな黒丸を囲む輪。その領域が完了したことを表す。
選択擬似状態ひし形。出ていく遷移に、分岐を選ぶガードを書く。
UML の記法:開始擬似状態は「ロック」を指し、どちらの状態にも自己ループがあり、「停止」で終了状態へ進む。Mermaid の行として状態遷移図 作成ツールに貼り付けた。ロック は 硬貨 / ロックを外す で 解除 へ遷移; 解除 は 押す / ロックする で ロック へ遷移; ロック は 停止 で へ遷移; ロック は 押す / 警報 で ロック へ遷移; 解除 は 硬貨 / お礼 で 解除 へ遷移硬貨式の回転ゲート硬貨 / ロックを外す押す / ロックする停止押す / 警報硬貨 / お礼ロック解除
UML の記法:開始擬似状態は「ロック」を指し、どちらの状態にも自己ループがあり、「停止」で終了状態へ進む。Mermaid の行として状態遷移図 作成ツールに貼り付けた。

状態遷移表の読み方

状態遷移表は、状態遷移図を表の形に書いたものです。1 状態 1 行、1 入力 1 列で、各セルにはマシンが移る状態を書きます。 → は開始状態、* は受理状態を表します。表と図は同じ情報をもつので、試験では一方からもう一方を求める問題がよく出ます。状態遷移図 作成ツールはどの図の下にもこの表を作ります。

状態遷移図 作成ツールが描いた、3 で割り切れる 2 進数の DFA。状態 ri は、それまでに読んだビットの余りが i であることを表す。r0 は 1 で r1 へ遷移; r1 は 0 で r2 へ遷移; r1 は 1 で r0 へ遷移; r2 は 0 で r1 へ遷移; r0 は 0 で r0 へ遷移; r2 は 1 で r2 へ遷移3 で割り切れる 2 進数の DFAstart101001r0r1r2
状態遷移図 作成ツールが描いた、3 で割り切れる 2 進数の DFA。状態 ri は、それまでに読んだビットの余りが i であることを表す。
状態入力 0入力 1
→ * r0r0r1
r1r2r0
r2r1r2
  • 行は「この状態で、この入力なら、ここへ」と読みます。r1 で 0 なら r2 へ。それまでに読んだビットを 2 倍すると余りが 2 になるからです。
  • DFA ではどのセルにもちょうど 1 つの状態が入ります。状態遷移図 作成ツールは足りない遷移を空のセル(横線)で示します。その DFA は部分 DFA で、教科書では死に状態を加えて完全にします。
  • NFA ではセルに {q0, q1} のような状態の集合か ∅ が入り、ε の列には入力を消費しない遷移を書きます。
  • ミーリマシンの表では各セルに次の状態 / 出力を書きます。マルコフ連鎖の表は遷移行列で、各行の合計は 1 になります。

ムーアマシンとミーリマシンの状態遷移図

ムーアマシンの出力はいまの状態だけで決まるので、出力を状態の中に書きます。ミーリマシンの出力は状態と入力で決まるので、矢印に入力/出力として書きます。 下の 2 つの図はどちらも、重なりを許して系列 101 を検出します。ミーリ版は 3 状態、ムーア版は 4 状態です。ムーアマシンでは「101 を見た直後」のための状態が別に必要だからです。状態遷移図 作成ツールは、9 行と 7 行の遷移から両方を描きました。

状態遷移図 作成ツールのムーアマシン。出力が 1 になるのは S3/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 を検出するムーアマシン(重なりあり)start10100101S0/0S1/0S2/0S3/1
状態遷移図 作成ツールのムーアマシン。出力が 1 になるのは S3/1 だけ。
状態遷移図 作成ツールのミーリマシン。1 を出力するのは、1/1 のラベルが付いた矢印 S2 → S1 だけ。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 を検出するミーリマシン(重なりあり)start1/00/01/10/00/01/0S0S1S2
状態遷移図 作成ツールのミーリマシン。1 を出力するのは、1/1 のラベルが付いた矢印 S2 → S1 だけ。
ムーアマシンミーリマシン
出力が決まる要素いまの状態だけいまの状態と入力
出力を書く場所状態の中:S3/1遷移の上:1/1
101 の検出に必要な状態数43
出力が変わるとき新しい状態に入ったときだけ入力が変わるとすぐ
状態遷移表では状態の横に 1 行 1 つの出力各セルに 次の状態 / 出力

学生とエンジニアが描く状態遷移図

どのカードからも、配置済みで状態遷移表付きの状態遷移図が上の状態遷移図 作成ツールに開き、そのまま編集やダウンロードができます。

TCP コネクションの状態遷移図

現行の TCP 規格である RFC 9293 は、コネクションを Figure 5 にまとめています。CLOSED から LISTEN、SYN-SENT、ESTAB を経て TIME-WAIT までの 11 状態で、どの矢印にもイベントとそれが引き起こすアクションが書かれています。RFC 自身、この図は「要約にすぎず、完全な仕様とみなしてはならない」と注意しています。ここの図は、状態遷移図 作成ツールがその Figure の 20 本の遷移から、原図と同じ上から下の向きで描いたものです。

状態遷移図 作成ツールで描いた、RFC 9293 の Figure 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 で CLOSED へ遷移TCP コネクションの状態遷移図(RFC 9293、Figure 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 の Figure 5 に基づく TCP コネクションの状態遷移図。

DFA の状態遷移図

DFA はもっとも単純な有限オートマトンで、オートマトンの演習では、3 で割り切れる 2 進数のようなある言語を受理する DFA を求めます。3 つの状態が余りを追い、r0 は開始状態であり受理状態でもあり、どの状態にも 0 と 1 の矢印が 1 本ずつあります。

ε 遷移のある NFA の状態遷移図

NFA では 1 つの記号に矢印が何本あってもよく、ε のラベルの矢印もあります。この NFA は a* ∪ b* を受理します。q0 からの 2 本の ε 遷移が枝を選び、q1 と q2 はどちらも受理状態です。

JK フリップフロップの状態遷移図

状態は Q=0 と Q=1 の 2 つ。Q=0 からは入力 JK = 0X で Q は 0 のまま、1X でセットされます。Q=1 からは X0 でそのまま、X1 でリセットされます。X はドントケアで、そのおかげで 4 通りの入力の組が 2 本ずつの矢印に収まります。

フリップフロップの回路そのものは回路図作成ツールで描く

カウンターの状態遷移図

2 ビットのアップダウンカウンターは 00、01、10、11 を輪のように回ります。入力 1 で 1 つ進み、入力 0 で 1 つ戻るので、となり合う状態の組にはどれも矢印が 2 本あります。

信号機の状態遷移図

UML 記法による時間制御のコントローラー。30 秒後に赤から青、25 秒後に青から黄、5 秒後に黄から赤になります。after は時間イベントを表す UML のキーワードです。

自動販売機の状態遷移図

ソフトウェア設計の定番の演習です。待機、硬貨受付、払出しの 3 状態で、商品選択の矢印にガード [残高 ≥ 価格]、スラッシュのあとにアクションを書きます。

注文ライフサイクルのステートマシン

業務オブジェクトにも状態があります。注文は注文受付から支払済み、発送済み、配達済みへ進むか、キャンセルか返金済みで終わります。どの終わりの状態も UML の終了状態へつながります。

マルコフ連鎖の状態遷移図

マルコフ連鎖では、どの矢印も確率をもち、1 つの状態から出る矢印の合計は 1 です。表は遷移行列になり、合計が 1 にならない行があれば作成ツールが知らせます。

2 ステップ分を確率の樹形図でたどる

状態遷移図の書き方

  1. 1

    状態と開始を書き出す

    状態遷移図 作成ツールに入力する前に、システムが待機しうる状態をすべて挙げます。オートマトンの記法ではそのうち 1 つが開始状態で、UML ではマシンは開始擬似状態から始まります。

  2. 2

    状態遷移図 作成ツールに遷移を入力する

    1 行に 1 つの遷移で、出ていく状態、入力やイベント、入る状態を書きます。入力するたびに状態遷移図が描き直され、同じ状態へ戻る遷移は自己ループになります。

  3. 3

    受理状態や終了状態を示す

    オートマトンなら accept: q2、UML の終了状態なら State --> [*] を加えます。状態遷移図 作成ツールのステータス行が、足りない遷移と到達しない状態を示します。

  4. 4

    表を確かめ、状態遷移図 作成ツールからダウンロード

    状態遷移表を自分の答えと比べ、必要なら上から下の向きや白黒に切り替え、状態遷移図 作成ツールから PNG、SVG、PDF で保存します。

状態遷移図 作成ツールのよくある質問

状態遷移図とステートマシン図の違いは?

+

同じ種類の図で、ステートマシン図は UML での呼び名です。 状態遷移図や状態図は、オートマトン理論や論理回路で使う一般的な呼び方です。ステートチャートは David Harel が入れ子の状態や並行状態を加えた拡張で、UML 2.5.1 の仕様は、そのステートマシンが Harel のステートチャートのオブジェクト指向版に基づくとしています。状態遷移図 作成ツールはどちらの記法でも単純なステートマシンを描きます。入れ子の状態は描きません。

開始状態と受理状態はどう指定する?

+

状態遷移図 作成ツールでは、start: q0 や accept: q2, q3 のように start: の行と accept: の行を加えます。 開始状態には何もないところからの矢印が、受理状態には二重丸が付きます。start: の行がなければ、最初に書いた状態が開始状態になります。UML の記法では、開始の遷移を [*] --> State、終了状態への遷移を State --> [*] と書きます。

状態遷移図で DFA と NFA はどう見分ける?

+

DFA の状態遷移図では、どの状態からも各入力記号の矢印がちょうど 1 本ずつ出ていて、ε のラベルはありません。それ以外は NFA です。 NFA では同じ記号の矢印が 2 本あったり、1 本もなかったり、ε 遷移があったりします。状態遷移図 作成ツールのステータス行は、描いたのがどちらかを示し、非決定的にしている状態と記号、または部分 DFA に足りない遷移を挙げます。

状態遷移図を状態遷移表にするには?

+

1 状態 1 行、1 入力記号 1 列にして、各セルに次の状態を書きます。状態遷移図 作成ツールは図の下にこの表を作ります。 開始状態には →、受理状態には * を付けます。NFA なら各セルは状態の集合、ミーリマシンなら次の状態 / 出力です。表はコピーするか CSV でダウンロードできます。

Mermaid や PlantUML の状態遷移図のコードは貼り付けられる?

+

できます。[*] --> Idle、Idle --> Running : start、Running --> [*] のような遷移の行は、そのまま状態遷移図 作成ツールに貼り付けられます。 stateDiagram-v2 のヘッダー、@startuml、ノート、向きの行は読み飛ばします。state X { … } で書いた複合状態は描かないので、内側の遷移を普通の行として並べてください。

状態遷移図とフローチャートは同じ?

+

違います。フローチャートは手順のステップを順に並べ、状態遷移図はシステムが待機する状態と、その間を動かすイベントを示します。 回転ゲートがステートマシンなのは、同じ「押す」がロック中と解除中で違う結果になるからです。UML でフローチャートにあたるのはアクティビティ図です。状態遷移図 作成ツールの回転ゲートの例で違いがわかります。

JK フリップフロップの状態遷移図はどんな形?

+

Q=0 と Q=1 の 2 状態に 4 本の矢印です。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 クレジットが無料で付きます。

状態遷移図 作成ツールで描いてみよう

遷移を入力し、表を確かめ、図をダウンロードするだけ。状態遷移図 作成ツールは無料で、アカウントも不要です。

状態遷移図 作成ツールを開く