この前の続き。
- DFAが受理する言語
- NFAが受理する言語
- 正則表現が表す言語
は全て正則言語である、というのを示すのがメインテーマ。
正則表現 => NFAの証明。正則表現に現われる演算子の数に関する帰納法で示す。分解していって、一個少ないから帰納法の仮定よりそれを満たすようなNFAを作れる(連接、閉包etcの3つの演算に関してこれをやる)。この証明がアルゴリズムっぽくなっているので、例はそれをやっていた(変形はやれるように練習しておかないと)。ただし、機械的に作るので冗長性が高くなっている(人間ならもっと簡単にできるんだが)。
逆のNFA => 正則表現を考える(これができたら表現できる集合が等しいことが言える)。その証明のために拡張NFAというものを考える。拡張NFAというのは、状態遷移図の矢印のラベルとして正則表現を許したものである(NFAの状態数を減らせるので、考えやすい)。NFAの状態数を減らしながら、拡張NFAだけにする。それができたら、そのラベルが求めたい正則表現になっている...はずというのが目標である。というわけで、NFAの状態数を減らしていくことを考える。
まず、任意のNFAを等価な以下を満たすNFAを作る(作り方はスライド参照)。
- 初期状態に入って来る矢印はない
- 受理状態は1つだけである
- 受理状態から出て行く矢印はない
実際のアルゴリズムは
- iからjへ向かう矢印を一本にまとめる
- 以下ステップが3つあるが、ややこしいのでスライド参照
という感じ。具体的な問題で練習すべし。