メモ。 subset construction を教科書のアルゴリズムに習って実装したもの。まだ汚いコードだ。疑似コードをそのままプログラムに落とせるようにしておいて、この次の dfa の状態数の最小化に備える。 not-marked とかやっている辺りがあまりにもどんくさい…

メモ。 Wikipedia http://en.wikipedia.org/wiki/Powerset_construction の Example 2 より。 まだ到達不能な状態を除去していないので冗長。 FA> (let ((nfa (def-nfa '(:a :b :c) '(0 1) ((:a (0 nil) (1 '(:b :c))) (:b (0 '(:a)) (1 nil)) (:c (0 '(:b))…

#<DFA: Q = {Q1 Q2 Q3} F = {Q2} q0 = Q1 Σ = {0 1} δ = state 0 1 ==================================== > Q1 Q1 Q2 *Q2 Q3 Q2 Q3 Q2 Q2 ></dfa:>

計算理論の基礎 オートマトンと言語(p.46) を見ると、計算の正確な定義というのが書いてある。これに合うように、微妙に定義を変えた。 finite-automaton クラスは定義通り５個組。内部に状態は持たない。 make-fa は make-instance をラップしたマクロ。FA …

よく考えたら遷移関数はただのグラフだった。グラフの隣接リスト表現で十分だ。マクロをちょっと書き換え、名前を付けられるようにし、ほとんどこれ以上短くできないようにした。 (defmacro def-dfa (name (states alphabet transition init-state final-sta…

オートマトンを勉強しよう。古典で基礎なので資料は山ほどある。だが基礎だから理解しているかというとそんなことはなかったので、手を動かした。http://www.sakabe.nuie.nagoya-u.ac.jp/~sakai/lecture/automata/ オートマトン・形式言語および演習より。以…