明瞭オートマトン

扱いやすい決定性オートマトンのこと。

1. スタートノードがひとつだけある。
2. ゴールノードがひとつだけある。
3. スタートノードとゴールノードは異なる（他の条件から出るが）。
4. すべてのノードはスタートノードから可達。（空集合は認識機械は除外）
5. すべてのノードからゴールノードに可達。
6. in(p) = 0 ⇔ p はスタートノード。
7. out(p) = 0 ⇔ p はゴールノード。
8. 上の2つから、すべての中間ノードは出る辺と入る辺の両方を持つ。
9. イプシロン辺はあってもよいが、各ノードから出るイプシロン辺は高々1本。
10. イプシロン辺からなるサイクルは存在しない。

１本のイプシロン辺からなるオートマトン (- → +) を単位オートマトン、1本の基本記号ラベル付きノードからなるオートマトンを基本オートマトンと呼ぶ。単位オートマトンと基本オートマトンは明瞭である。

次の条件を定義する。

1. 明瞭連接条件
2. 明瞭ユニオン条件
3. 明瞭オプショナル条件
4. 明瞭繰り返し条件

これらの条件を満たすときの連接、ユニオン、オプショナル、繰り返しが明瞭性を保存することを証明する。

されに次の条件を考える。

• 行き先がゴールノードでないイプシロン辺は存在しない。

この条件を満たすとき、最小イプシロン形と呼ぶ。イプシロン辺の可能なら縮約（両端のノードを同一視）、除去（辺だけ取り除く）により、最小イプシロン形にできる。行き先がゴールであるイプシロン辺には手を付けない。

1. イプシロン辺を見つける
2. まとめて処理するためにイプシロン辺の最長チェーン（パス）を作る。サイクルがないので、最長チェーンは作れる。
3. チェーンの先の方から逆向きに見ていく。
4. 辺の行き先がゴールなら何もしない。
5. 行き先に入る辺がないなら縮約する
6. 短絡辺を生成してイプシロン辺を取り除く

pから出る辺のラベルを集めて OutL(p)を作れる。pからイプシロン辺でたどれるノードの OutL(q) を全部集めてNexL(p)を作る。最小イプシロン形なら、OutL(p)とNextL(p)が一致する。ほんとに重要なのはこの点で、次が望ましい。

1. 任意のノードpに関して NexL(p) = OutL(p)
2. Next(p)（OutL(p)である）上で定義された遷移先ノードを値とする関数が決定性になる。

これなら、遷移を表すデータにハッシュマップの配列を使える。カレントノード番号をインデックスとしてアクセスし、得られたハッシュテーブル（ディクテーション、オブジェクト）を入力記号で引いて遷移先を一意に決められる。