正規表現の可視化
正規表現を NFA（トンプソンの構成法）・DFA（部分集合構成法）・最小 DFA に変換して状態遷移図を描き、文字列を 1 文字ずつ照合する様子を見せます。バックトラック型のエンジンで時間が爆発する ReDoS の例も比べられます。
例
教科書でおなじみの例。a と b の並びで、最後が abb のもの
- NFA の状態
- 14
- DFA の状態
- 5
- 最小 DFA の状態
- 4
- 文字のクラス
- 2
0 / 6 文字: 状態 A にいる
丸が状態、二重丸が受理状態です。DFA ではいつも 1 つの状態にいます。行き先のない文字を読むと行き止まり（図には描かない状態）になります。
遷移表
部分集合構成法では、NFA の状態の集合を 1 つの DFA の状態にします。列は文字のクラス（どの遷移でも同じように扱われる文字の集まり）です。「—」は行き止まりです。
| 状態 | NFA の状態 | a | b |
|---|---|---|---|
| → A | {0, 1, 2, 3, 4, 5} | B | C |
| B | {1, 2, 3, 4, 5, 6, 8, 9, 10} | B | D |
| C | {1, 2, 3, 4, 5, 7, 9} | B | C |
| D | {1, 2, 3, 4, 5, 7, 9, 11, 12} | B | E |
| E ◎ | {1, 2, 3, 4, 5, 7, 9, 13} | B | C |
→ は開始状態、◎ は受理状態です。
照合の手間の比べ方
「aababb」全体を照合したときの手間です。
| 方式 | 結果 | 手間 | 数え方 |
|---|---|---|---|
| DFA | 一致 | 6 | 1 文字につき遷移を 1 回たどる |
| NFA（同時にたどる） | 一致 | 51 | 1 文字ごとに、今いる状態の数だけ調べる |
| バックトラック | 一致 | 27 | 構文の要素を 1 つ試すごとに 1（JavaScript などのエンジンと同じ考え方） |
使い方
- 正規表現と、照合する文字列を入力します。例のボタンを押すと、よく使う正規表現を呼び出せます。
- 「NFA」「DFA」「最小 DFA」で表示する図を切り替えます。「再生」や「◀」「▶」、文字列のマスを押すと、1 文字ずつ読んで状態が移る様子を確かめられます。
- 使えるのは、文字・.・[...] と [^...]・\d \w \s（と大文字の否定）・|・() と (?:)・* + ?・{n} {n,} {n,m}（20 回まで）です。^ $・後方参照・先読み・最短一致など、DFA で表せないか、このアプリで扱わないものは使えません。
- キーボードでは ← → で 1 文字戻る / 進む、Home / End で最初 / 最後に移ります（入力欄にカーソルがないとき）。
NFA と DFA
正規表現は、状態と遷移でできた有限オートマトンに変換できます。トンプソンの構成法では、1 文字を「2 つの状態と 1 本の遷移」にし、連結・選択（|）・繰り返し（*）を ε 遷移（文字を読まずに移れる遷移）でつなぎ合わせて NFA（非決定性有限オートマトン）を作ります。NFA は同時に複数の状態にいられるので、照合では「今いる状態の集合」を 1 文字ずつ更新します。
部分集合構成法では、この「NFA の状態の集合」を 1 つの状態とみなして DFA（決定性有限オートマトン）を作ります。DFA はいつも 1 つの状態にいるので、1 文字につき遷移を 1 回たどるだけで照合できます。ただし状態の数は、最悪の場合 NFA の状態の数の指数になります（例の「(a|b)*a(a|b){2}」は、後ろの 3 文字を覚えておくために 8 状態が必要です）。
最小化では、どんな続きの文字列についても受理するかどうかが同じになる状態をまとめ、同じ言語を受理する一番小さな DFA を作ります。同じ言語を表す正規表現は、書き方が違っても最小 DFA は同じ形になります。
バックトラックと ReDoS
JavaScript・Python・Java など多くの正規表現エンジンは、オートマトンではなくバックトラックで照合します。正規表現を先頭から試し、失敗したら直前の分かれ道に戻って別の道を試すやり方で、後方参照のような便利な機能を実現できます。その代わり「(a+)+b」のように同じ文字列を何通りにも分けられる正規表現では、一致しない文字列に対して分け方をすべて試すため、時間が文字数の指数で増えます。これを悪用してサーバーを止める攻撃が ReDoS（正規表現によるサービス拒否）です。