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