Automaton

Haskellで有限オートマトンを実装する †

• オートマトンの受理言語を計算するプログラム
  (sstar s1) はアルファベットs1上の文字列全体の集合を表わし,
  accepts delta1 s1_0 f1 (sstar s1) は受理言語の集合となる.
  いずれも無限集合の可能性があるので, take関数で必要な個数だけ取ってくる.
  automaton.lhs

  -- 有限オートマトンは次の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ファイル)
  m1.dot
  m2.dot

• automaton.lhsをpdfにしたファイル
  automaton.pdf

関連ページ †

• Graphviz (HaskellのGraphクラスとGraphvizの使い方)

リンク †

• Graphviz (dotファイルの表示・変換) by graphviz.org
• Haskell Documents (dotファイル出力) by haskell.org