正規表現とかオートマトンとか -Courseraの授業の復習を兼ねて-

Courseraの授業の復習を兼ねて、とか言ってますがグラフ描きたいだけです。ごめんなさい。

さて。CourseraではMachine Learningの他にAutomataとかCompilersとかも取っているのですが、割と内容がかぶってるので冗長で時間の無駄良い感じに復習になって有難いです。

CourseraでAutomata,Compilers両コースを同時受講していてものすごく冗長な感じがしている（違いはKleene*をε-NFAで表現する時の戻る方向の弧の着地点程度）、そして正規表現→NFA→DFA変換のコードをまた書いてるこれ何度目だ的な #coursera

— naoya tさん (@naoya_t) 5月 16, 2012

クリーネ閉包のNFA表現がUllman先生とAiken先生でちょっと違うのだけれど、この違いは何かに影響を及ぼすのでしょうか。

1. Automata (Jeffrey Ullman教授) における a*

2. Compilers (Alex Aiken教授) における a*

このグラフはみんな大好きGraphvizで描いてるんだけど、当然dotファイルは手書きなんかしませんよね。

(set! *ullman* #t)
(fa-draw (string->NFA "a*") "a*" "a-star-ullman.gif")
(set! *ullman* #f)
(fa-draw (string->NFA "a*") "a*" "a-star-aiken.gif")

みたいな感じです。
string->NFA で正規表現を等価なNFAグラフに変換して、そのグラフからdotファイルを生成し、graphvizでgif化しています。
何年か前にもこういうコードを書いた覚えがありますが気のせいでしょう。
Schemeコードはエントリ末尾に貼ります。

講義で使われる正規表現は普段使ってるみたいな [ab]*c 的表記ではなく (a+b)*c みたいなやつですがまあどちらでも。

(fa-draw (string->NFA "(a+b)*c") "(a+b)*c" "abc1.gif")
(fa-draw (regexp->NFA "[ab]*c") "[ab]*c" "abc2.gif")

正規表現を等価なNFAに変換してからのDFAへの変換も

;; "(1+0)*1"
(define rx1 (Concat (Kleene* (Union (Single 1) (Single 0))) (Single 1)))
(fa-draw rx1 "(1+0)*1" "rx1.gif")
(fa-draw (NFA->DFA rx1) "DFA for (1+0)*1" "rx1-dfa.gif")
;; "(1+0)*1(1+0)*"
(define rx2 (Concat (Kleene* (Union (Single 1) (Single 0))) (Single 1) (Kleene* (Union (Single 1) (Single 0)))))
(fa-draw rx2 "(1+0)*1(1+0)*" "rx2.gif")
(fa-draw (NFA->DFA rx2) "DFA for (1+0)*1(1+0)*" "rx2-dfa.gif")

(fa-draw (regexp->NFA "[ab][c-e]") "[ab][c-e]" "abc-e.gif")
(fa-draw (NFA->DFA (regexp->NFA "[ab][c-e]")) "DFA for [ab][c-e]" "abc-e-dfa.gif")

regexp->NFA のブラケットのパースは [A-Za-z] には対応してるけど [^A-Z] には対応させてないです（今の目的そこじゃないし）

コード

Courseraには宿題の答えをWebとかに貼ってはいけないというHonor code（倫理規定）があるので、万が一課題とかぶったら非公開にするかもです。
https://github.com/naoyat/automata