読者です 読者をやめる 読者になる 読者になる

naoya_t@hatenablog

いわゆるチラシノウラであります

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

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

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


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

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

f:id:n4_t:20120516190641g:plain

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

f:id:n4_t:20120516190653g:plain
このグラフはみんな大好き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")

f:id:n4_t:20120516191639g:plain
f:id:n4_t:20120516191651g:plain

正規表現を等価な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")

f:id:n4_t:20120516193004g:plain
f:id:n4_t:20120516193023g:plain
f:id:n4_t:20120516193038g:plain
f:id:n4_t:20120516193053g:plain

(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")

f:id:n4_t:20120516191219g:plain
f:id:n4_t:20120516191232g:plain
regexp->NFA のブラケットのパースは [A-Za-z] には対応してるけど [^A-Z] には対応させてないです(今の目的そこじゃないし)

コード

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