正則言語と正則表現

この前の続き。

  • DFAが受理する言語
  • NFAが受理する言語
  • 正則表現が表す言語

は全て正則言語である、というのを示すのがメインテーマ。

正則表現 => NFAの証明。正則表現に現われる演算子の数に関する帰納法で示す。分解していって、一個少ないから帰納法の仮定よりそれを満たすようなNFAを作れる(連接、閉包etcの3つの演算に関してこれをやる)。この証明がアルゴリズムっぽくなっているので、例はそれをやっていた(変形はやれるように練習しておかないと)。ただし、機械的に作るので冗長性が高くなっている(人間ならもっと簡単にできるんだが)。

逆のNFA => 正則表現を考える(これができたら表現できる集合が等しいことが言える)。その証明のために拡張NFAというものを考える。拡張NFAというのは、状態遷移図の矢印のラベルとして正則表現を許したものである(NFAの状態数を減らせるので、考えやすい)。NFAの状態数を減らしながら、拡張NFAだけにする。それができたら、そのラベルが求めたい正則表現になっている...はずというのが目標である。というわけで、NFAの状態数を減らしていくことを考える。

まず、任意のNFAを等価な以下を満たすNFAを作る(作り方はスライド参照)。

  1. 初期状態に入って来る矢印はない
  2. 受理状態は1つだけである
  3. 受理状態から出て行く矢印はない

実際のアルゴリズムは

  • iからjへ向かう矢印を一本にまとめる
  • 以下ステップが3つあるが、ややこしいのでスライド参照

という感じ。具体的な問題で練習すべし。