自分の理解力の無さから、参考にしようとしていたサイトの説明では行き詰ってしまった。なのでオートマトンの教科書を読んでみた。
ε動作ありのNFAから、ε動作なしのNFAへの変換のやり方が書いてあったので、やってみた。
まず-
（ε閉包というらしい）というものを定義してみる。これは状態
からε動作だけで到達できる状態の集合（ただし
自身の含む）を表す。
| 状態 |
|
|---|---|
状態集合Xに対して、-
-
を定義する。これを踏まえて、元のオートマトン
から新しいオートマトン
を作れば、それがε遷移を含まないNFAになっているのだと。
ε動作を許さないNFAの状態遷移
新しい状態遷移関数をとすると、
-
-
となる。
の定義を元に、例として、状態
で入力Yの場合の遷移を求めると以下の通り。
-
-
-
-
新しい状態遷移関数を元に状態遷移表つくってみた。
| 状態 |
X | Y | Z | . |
|---|---|---|---|---|
ε動作を許さないNFAの受理状態集合
新しい受理状態集合は以下の通り。
-
のとき：
のとき：
したがって、この例では、