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