sinya8282 読むもの - 昏論会ウィキ

DFA minimisation using the Myhill-Nerode theorem

内容

与えられたDFAが認識する正則言語の同値類の個数は, 実はそのDFAと等価な最小DFAの状態数なのだ! という Myhill-Nerode の定理とそれを前提としたDFA最小化の手続き紹介.

感想

同値類の個数 = 最小DFAの個数ってのは直感的で綺麗な定理.
DFAベースな正規表現エンジンに最小化を組み込もうか迷ってここらへんの論文を読んでみた. 実装は簡単ぽいけど, マッチング速度の高速化とは無縁なんだよなぁ.

From Regular Expressions to DFA's Using Compressed NFA's

内容

タイトルそのまま, 正規表現からDFAへの変換手法の話.
僕の大好きな grep 実装 cgrep の中の話っぽいので読んでみた.
といいたいところだけど120P超あるので, 正規表現からNFA変換の部分だけ読んだ.

McNaughton and Yamada's NFA

正規表現のパースツリーにそのまま付加情報を追加してNFAを構成する手法(cgrep で使われてる).
この手法だと正規表現Rの長さ|R|でなくR中のリテラルの個数Aな空間効率O(A)でNFAを作れる.

感想

先に実装を読んでたので, 特に発見はない! 論文の付録にあるGNU grep vs cgrep なベンチマークが面白い.
流し読みでも全部読んだ方が良さそうだなぁ.