Haskellで有限オートマトンを実装する †
- オートマトンの受理言語を計算するプログラム
(sstar s1) はアルファベットs1上の文字列全体の集合を表わし,
accepts delta1 s1_0 f1 (sstar s1) は受理言語の集合となる.
いずれも無限集合の可能性があるので, take関数で必要な個数だけ取ってくる.
-- 有限オートマトンは次の5つ組 M = (s1, q1, delta1, s1_0, f1)
s1 = ['a','b'] q1 = [1,2] s1_0 = 1 f1 = [2]
delta1::State->Char->State
delta1 1 'a' = 1
delta1 1 'b' = 2
delta1 2 'a' = 2
delta1 2 'b' = 1
-- 以下は実行例
-- *Main> take 10 (sstar s1)
-- ["","a","b","aa","ab","ba","bb","aaa","aab","aba"]
-- *Main> take 10 $ accepts delta1 s1_0 f1 (sstar s1)
-- ["b","ab","ba","aab","aba","baa","bbb","aaab","aaba","abaa"]
- オートマトンのグラフ (Grphvizのdotファイル)
関連ページ †
- Graphviz (HaskellのGraphクラスとGraphvizの使い方)
リンク †
Counter: 4318,
today: 1,
yesterday: 0