状態遷移図 作成ツール ステートマシン図と有限オートマトン
オートマトンの授業、論理回路、ソフトウェア設計のための無料の状態遷移図 作成ツールです。1 行に 1 つ遷移を書くだけで、有限オートマトンや UML のステートマシン図が自動で配置され、開始の矢印、受理状態の二重丸、自己ループ、状態遷移表まで描かれます。
遷移は q0 -a-> q1、q0 -> q1 : a、またはスプレッドシートの 3 列で書きます。start: と accept: の行を加えます。同じ矢印をたどる入力は "0, 1" のようにまとめます。start: の行で別の状態を指定しない限り、状態遷移図 作成ツールは最初の状態を開始状態とみなします。
3 状態、6 遷移、入力アルファベット {0, 1}。どの状態も各記号でちょうど 1 つの遷移をもつので、完全な DFA です。
状態遷移図 作成ツールはこのブラウザのタブ内でマシンを配置します。アカウントもアップロードも不要で、ファイルは自由に使えます。
| 状態 | 入力 0 | 入力 1 |
|---|---|---|
| → q0 | q1 | q0 |
| q1 | q1 | q2 |
| * q2 | q1 | q0 |
状態遷移図のスタイル
AI 状態遷移図ジェネレーターの 4 つの仕上がりを、それぞれ別のマシンで紹介します。教科書風のムーア型系列検出器、ホワイトボードの押しボタン式信号、各状態にアイコンを入れたネット注文、発表用ダークスライドのエレベーター制御です。カードを選ぶと、その遷移がコンポーザーに読み込まれます。
状態遷移図の例
状態遷移図 作成ツールの AI ジェネレーターで描いた状態遷移図の例を 8 つ紹介します。自動販売機、TCP コネクションの状態、DFA、マルコフ連鎖と、4 つの仕上がりです。どれも実際に描いた画像で、描いたプロンプトが付いています。カードを選ぶとプロンプトを読み込みます。
どの矢印にもトリガー [ガード] / エフェクトを書いた自動販売機の UML ステートマシン図。状態遷移図 作成ツールの AI 側で作成。
RFC 9293 に基づく TCP コネクションの状態遷移図を状態遷移図 作成ツールで描画。CLOSED から TIME-WAIT までの 11 状態と、すべてのイベントとアクション。
3 で割り切れる 2 進数を受理する DFA。開始の矢印と受理状態の二重丸付きで、状態遷移図 作成ツールが描画。
どの矢印にも遷移確率を書いた毎日の天気のマルコフ連鎖。状態遷移図 作成ツールの AI ジェネレーターで作成。
状態遷移図 作成ツールの 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 のように矢印に入力/出力を書く。出力は状態ではなく遷移に属する。 |
| 記号 | 名前 | 意味 |
|---|---|---|
| 開始擬似状態 | 小さな黒丸。そこから出る 1 本の遷移にはトリガーもガードも付けない。 | |
| 状態 | 角の丸い四角形に状態名を書く。任意の区画に entry /、do /、exit / の振る舞いを書ける。 | |
| e [g] / a | 遷移 | トリガー [ガード] / エフェクト。どの部分も省略可。例:硬貨 / ロックを外す、商品選択 [残高 ≥ 価格] / 商品を出す。 |
| 終了状態 | 小さな黒丸を囲む輪。その領域が完了したことを表す。 | |
| 選択擬似状態 | ひし形。出ていく遷移に、分岐を選ぶガードを書く。 |
状態遷移表の読み方
状態遷移表は、状態遷移図を表の形に書いたものです。1 状態 1 行、1 入力 1 列で、各セルにはマシンが移る状態を書きます。 → は開始状態、* は受理状態を表します。表と図は同じ情報をもつので、試験では一方からもう一方を求める問題がよく出ます。状態遷移図 作成ツールはどの図の下にもこの表を作ります。
| 状態 | 入力 0 | 入力 1 |
|---|---|---|
| → * r0 | r0 | r1 |
| r1 | r2 | r0 |
| r2 | r1 | r2 |
- 行は「この状態で、この入力なら、ここへ」と読みます。r1 で 0 なら r2 へ。それまでに読んだビットを 2 倍すると余りが 2 になるからです。
- DFA ではどのセルにもちょうど 1 つの状態が入ります。状態遷移図 作成ツールは足りない遷移を空のセル(横線)で示します。その DFA は部分 DFA で、教科書では死に状態を加えて完全にします。
- NFA ではセルに {q0, q1} のような状態の集合か ∅ が入り、ε の列には入力を消費しない遷移を書きます。
- ミーリマシンの表では各セルに次の状態 / 出力を書きます。マルコフ連鎖の表は遷移行列で、各行の合計は 1 になります。
ムーアマシンとミーリマシンの状態遷移図
ムーアマシンの出力はいまの状態だけで決まるので、出力を状態の中に書きます。ミーリマシンの出力は状態と入力で決まるので、矢印に入力/出力として書きます。 下の 2 つの図はどちらも、重なりを許して系列 101 を検出します。ミーリ版は 3 状態、ムーア版は 4 状態です。ムーアマシンでは「101 を見た直後」のための状態が別に必要だからです。状態遷移図 作成ツールは、9 行と 7 行の遷移から両方を描きました。
| ムーアマシン | ミーリマシン | |
|---|---|---|
| 出力が決まる要素 | いまの状態だけ | いまの状態と入力 |
| 出力を書く場所 | 状態の中:S3/1 | 遷移の上:1/1 |
| 101 の検出に必要な状態数 | 4 | 3 |
| 出力が変わるとき | 新しい状態に入ったときだけ | 入力が変わるとすぐ |
| 状態遷移表では | 状態の横に 1 行 1 つの出力 | 各セルに 次の状態 / 出力 |
学生とエンジニアが描く状態遷移図
どのカードからも、配置済みで状態遷移表付きの状態遷移図が上の状態遷移図 作成ツールに開き、そのまま編集やダウンロードができます。
TCP コネクションの状態遷移図
現行の TCP 規格である RFC 9293 は、コネクションを Figure 5 にまとめています。CLOSED から LISTEN、SYN-SENT、ESTAB を経て TIME-WAIT までの 11 状態で、どの矢印にもイベントとそれが引き起こすアクションが書かれています。RFC 自身、この図は「要約にすぎず、完全な仕様とみなしてはならない」と注意しています。ここの図は、状態遷移図 作成ツールがその Figure の 20 本の遷移から、原図と同じ上から下の向きで描いたものです。
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 にならない行があれば作成ツールが知らせます。
状態遷移図の書き方
- 1
状態と開始を書き出す
状態遷移図 作成ツールに入力する前に、システムが待機しうる状態をすべて挙げます。オートマトンの記法ではそのうち 1 つが開始状態で、UML ではマシンは開始擬似状態から始まります。
- 2
状態遷移図 作成ツールに遷移を入力する
1 行に 1 つの遷移で、出ていく状態、入力やイベント、入る状態を書きます。入力するたびに状態遷移図が描き直され、同じ状態へ戻る遷移は自己ループになります。
- 3
受理状態や終了状態を示す
オートマトンなら accept: q2、UML の終了状態なら State --> [*] を加えます。状態遷移図 作成ツールのステータス行が、足りない遷移と到達しない状態を示します。
- 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 と NFA はどう見分ける?
+DFA の状態遷移図では、どの状態からも各入力記号の矢印がちょうど 1 本ずつ出ていて、ε のラベルはありません。それ以外は NFA です。 NFA では同じ記号の矢印が 2 本あったり、1 本もなかったり、ε 遷移があったりします。状態遷移図 作成ツールのステータス行は、描いたのがどちらかを示し、非決定的にしている状態と記号、または部分 DFA に足りない遷移を挙げます。
状態遷移図を状態遷移表にするには?
+
状態遷移図を状態遷移表にするには?
+1 状態 1 行、1 入力記号 1 列にして、各セルに次の状態を書きます。状態遷移図 作成ツールは図の下にこの表を作ります。 開始状態には →、受理状態には * を付けます。NFA なら各セルは状態の集合、ミーリマシンなら次の状態 / 出力です。表はコピーするか CSV でダウンロードできます。
Mermaid や PlantUML の状態遷移図のコードは貼り付けられる?
+
Mermaid や PlantUML の状態遷移図のコードは貼り付けられる?
+できます。[*] --> Idle、Idle --> Running : start、Running --> [*] のような遷移の行は、そのまま状態遷移図 作成ツールに貼り付けられます。 stateDiagram-v2 のヘッダー、@startuml、ノート、向きの行は読み飛ばします。state X { … } で書いた複合状態は描かないので、内側の遷移を普通の行として並べてください。
状態遷移図とフローチャートは同じ?
+
状態遷移図とフローチャートは同じ?
+違います。フローチャートは手順のステップを順に並べ、状態遷移図はシステムが待機する状態と、その間を動かすイベントを示します。 回転ゲートがステートマシンなのは、同じ「押す」がロック中と解除中で違う結果になるからです。UML でフローチャートにあたるのはアクティビティ図です。状態遷移図 作成ツールの回転ゲートの例で違いがわかります。
JK フリップフロップの状態遷移図はどんな形?
+
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 ジェネレーターでイラスト入りや手描き風の状態遷移図は描ける?
+描けます。状態遷移図 作成ツールの隣の AI ジェネレーターは、教科書、ホワイトボード、イラスト入り、ダークスライドの版を描き、紙に描いた状態遷移図の写真も描き直します。 無料の状態遷移図 作成ツールから送った遷移は、状態と矢印の正確なリストとしてモデルに渡されるので、マシンを勝手に作らずそのまま写します。新規アカウントには 100 クレジットが無料で付きます。
出典
- Unified Modeling Language 2.5.1、14 章 ステートマシン(記法は 14.2.4) — Object Management Group
- 決定性有限オートマトン、CS/ECE 374 講義ノート — University of Illinois Urbana-Champaign
- RFC 9293 Transmission Control Protocol、3.3.2 節 ステートマシンの概要 — IETF
関連ツールと記事
ほかの図表作成ツールと、その読み方をまとめた記事。