正規表現をDFAに変換（NFA・部分集合構成・最小DFA）
正規表現をトンプソンNFA、部分集合構成のDFA、最小DFAに変換し、遷移表を表示して、文字列の受理・拒否をテストします。
アルファベットは、式で使われている記号の集合です：a, b。
最小DFAの状態名は、統合したDFAの状態名に由来します。"—"は存在しない遷移、つまり入力が拒否されることを表します。
| 状態 | ε | a | b |
|---|---|---|---|
| → 0 | {1,2} | — | — |
| 1 | {3,4} | — | — |
| 2 | — | {5} | — |
| 3 | — | {6} | — |
| 4 | — | — | {7} |
| 5 | — | — | {8} |
| 6 | {9} | — | — |
| 7 | {9} | — | — |
| 8 | — | — | {10} |
| 9 | {1,2} | — | — |
| * 10 | — | — | — |
| 状態 | NFAの状態数 | a | b |
|---|---|---|---|
| → A | {0,1,2,3,4} | B | C |
| B | {1,2,3,4,5,6,9} | B | D |
| C | {1,2,3,4,7,9} | B | C |
| D | {1,2,3,4,7,8,9} | B | E |
| * E | {1,2,3,4,7,9,10} | B | C |
| 状態 | a | b |
|---|---|---|
| → AC | B | AC |
| B | B | D |
| D | B | E |
| * E | B | AC |
| 文字列 | 結果 | DFAの経路 |
|---|---|---|
| abb | 受理 | A → B → D → E |
| aabb | 受理 | A → B → B → D → E |
| babb | 受理 | A → C → B → D → E |
| ab | 拒否 | A → B → D |
| abba | 拒否 | A → B → D → E → B |
コンパイラやオートマトンの授業では、正規表現を3段階で機械に変換します。トンプソン構成でε遷移のあるNFAを作り、部分集合構成でDFAに変え、最小化で同じ動作をする状態をまとめます。このツールは、形式的な正規表現についてこの3段階をすべて行い、各機械の遷移表を、開始状態と受理状態の印とともに表示し、そのうえでテスト用の文字列を最小DFAに通して、それぞれがたどる経路を示します。
使い方
- |・*・+・?・括弧・ε（またはeps）を使って正規表現を入力します。
- +が「1回以上」か、教科書によっては「または」かを選びます。
- テストする文字列を1行に1つ入力します（空行は空文字列のテスト）。
- NFA・DFA・最小DFAの表と、受理／拒否の結果を確認します。
計算式
DFAの状態 = NFAの状態集合のε閉包 · move(T, a) = Tからaで到達できるNFAの状態 · 最小DFA = 以後の動作が同じ状態のクラス
トンプソン構成では、各記号に状態を2つ与え、|・*・+・?のたびに状態を2つ加えます。連接では、ドラゴンブックと同様に、前の部分の終端と次の部分の先頭を統合します。部分集合構成では、DFAの状態を見つけた順にA、B、C…と名付けます。最小化は、受理／非受理の分割から始め、グループ内の状態がどの記号でも同じグループへ遷移するまで分割を細かくします（ムーアのアルゴリズム。ホップクロフトのアルゴリズムと同じ結果）。死状態は存在しない遷移を集めるもので、表示も非表示もできます。
計算例
(a|b)*abbでは、トンプソン構成はNFAの状態11個を作ります。部分集合構成はDFAの状態をAからEの5個作り、遷移はドラゴンブックの表とまったく同じで、受理状態はEだけです。AとCは同じ動作をするため、最小DFAはAC、B、D、Eの4状態になります。テスト文字列のうち、abb・aabb・babbは受理され、abとabbaは拒否されます。
よくある質問
DFAがNFAより状態が多くなることがあるのはなぜですか？
DFAの状態は、NFAの状態の集合1つに対応し、そのような集合は最大2ⁿ個あり得ます。通常は到達できるのは少数ですが、式によっては本当に指数的な数が必要になり、このツールは2,000個で停止します。
プログラミング言語の正規表現と同じですか？
いいえ。これはオートマトン理論の形式的な表記で、和・連接・スター・プラス・オプションだけがあります。後方参照や先読みのような機能は正規ではなく、DFAに変換できません。
死状態とは何ですか？
どの記号でも自分自身に戻る非受理状態で、「この入力は決して受理されない」ことを表します。表では省略されることが多く、オプションをオンにすると表示されます。
出典
最終更新:
この入力内容のページアドレス： https://kakao.mobile/ja/tools/regex-to-dfa-tool/
このツールを引用する
kakaoCalc. (2026, November 8). 正規表現をDFAに変換（NFA・部分集合構成・最小DFA）. https://kakao.mobile/ja/tools/regex-to-dfa-tool/
“正規表現をDFAに変換（NFA・部分集合構成・最小DFA）.” kakaoCalc, 8 Nov. 2026, kakao.mobile/ja/tools/regex-to-dfa-tool/.