Automaton - PukiWiki

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

m1.png
  • オートマトンの受理言語を計算するプログラム
    (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: 4209, today: 1, yesterday: 0

添付ファイル: filem1.png 754件 [詳細] fileautomaton.lhs 866件 [詳細] fileautomaton.pdf 1737件 [詳細] filem2.dot 870件 [詳細] filem1.dot 887件 [詳細]

トップ   編集 凍結 差分 バックアップ 添付 複製 名前変更 リロード   新規 一覧 単語検索 最終更新   ヘルプ   最終更新のRSSPDF
Last-modified: 2006-12-04 (月) 00:31:43 (4493d)