オートマトンのゴールノード

正規表現の部分式に対応するオートマトンと完全な構文単位に対応するオートマトンを区別する必要があるのだった。

最初に、終状態ノードとゴールノードを区別することからはじめる。終状態はそこで終端記号が入力すると受理が成功するような状態のこと。これはいいよね。ゴールノードとは、終状態において実際に終端記号の入力が起きた時の遷移先。よって、ゴールノードとは、次の条件を満たす。

1. 入る辺のラベルはすべて'$'。
2. 出る辺はない。
3. 終状態からゴールノードに至る辺以外では'$'は出現しない。

別な言い方をすると：

1. 終状態とは、'$'でラベルされた出る辺を持つノードである。
2. '$'でラベルされた辺の先は必ず特定のノードでなくてはならない。

形式的に書くために次を定義しておく。

1. グラフのノードpに対して、in(p) は、pのin-次数
2. グラフのノードpに対して、out(p) は、pのout-次数
3. 辺ラベル付きグラフのノードpに対して、InL(p) は、pへ入る辺のラベルの集合
4. 辺ラベル付きグラフのノードpに対して、OutL(p) は、pから出る辺のラベルの集合

'-'はスタートノード、'+'はゴールノードも表すとする。で、先の条件をもう一度記述すると：

1. InL('+') = {$}
2. out('+') = 0
3. 任意のpに対して、$∈InL(p) ならば p = '+'

• pが終状態 ⇔ $∈OutL(p)

終状態から$による遷移先が'+'に限ることはすぐ出る。