« ブログの内容は鵜呑みにしない方がいいですよ(笑) | トップページ | 素数日を求める »

2012年4月 5日 (木)

オートマトン

ネットをウロウロしてたら、こちらのブログを発見しました。

「オートマトン」って、詳しくは知らないけど何だか面白そうです。 参考に挙げてあったPDFファイルを見ながら、自分なりにコードを書いてみました。

{-
   << DFA(決定性有限オートマトン) >>

   参考:
   http://d.hatena.ne.jp/cranebird/20120327/1332857936
   http://kurt.scitec.kobe-u.ac.jp/~kikyo/lec/07/automaton/k2.pdf
-}

type Q     = String
type Delta = ((Q, Char), Q)

-- isAccept 遷移表 受理状態の集合 状態 文字列 => 真偽
isAccept :: [Delta] -> [Q] -> Q -> String -> Bool
isAccept qs f st []        = elem st f
isAccept qs f st (c : cs)  = isAccept qs f st' cs
  where Just st' = lookup (st, c) qs -- 遷移表に抜けがないことが前提

-- makeDfa 遷移表 受理状態の集合 初期状態 => dfa
makeDfa :: [Delta] -> [Q] -> Q -> String -> String
makeDfa qs f q0 cs = if (isAccept qs f q0 cs)
                     then "Accept"
                     else "Not Accept"


{-
   例 1
   Σ = {a}, 奇数個の 'a' からなる文字列を受理する
-}
dfa1 :: String -> String
dfa1 = makeDfa qs f "Even"
  where
    qs = [(("Even", 'a'), "Odd"), (("Odd", 'a'), "Even")]
    f  = ["Odd"]

{-
   例 2
   Σ = {a, b}, 奇数個の 'a' からなる文字列を受理する
-}
dfa2 :: String -> String
dfa2 = makeDfa qs f "Even"
  where
    qs = [(("Even", 'a'), "Odd"), (("Even", 'b'), "Even"),
          (("Odd", 'a'), "Even"), (("Odd", 'b'), "Odd")]
    f  = ["Odd"]

{-
   例 3
   Σ = {a, b}, 奇数個の a と偶数個の b からなる文字列を受理する
   (0 は偶数とする)
-}
dfa3 :: String -> String
dfa3 = makeDfa qs f "00"
  where
    qs = [(("00", 'a'), "10"), (("00", 'b'), "01"),
          (("10", 'a'), "00"), (("10", 'b'), "11"),
          (("01", 'a'), "11"), (("01", 'b'), "00"),
          (("11", 'a'), "01"), (("11", 'b'), "10")]
    f  = ["10"]

{-
   問 4
   Σ = {a, b, c}, 奇数個の a と偶数個の b からなる文字列を受理する
   (0 は偶数とする)
-}
dfa4 :: String -> String
dfa4 = makeDfa qs f "00"
  where
    qs = [(("00", 'a'), "10"), (("00", 'b'), "01"), (("00", 'c'), "00"),
          (("10", 'a'), "00"), (("10", 'b'), "11"), (("10", 'c'), "10"),
          (("01", 'a'), "11"), (("01", 'b'), "00"), (("01", 'c'), "01"),
          (("11", 'a'), "01"), (("11", 'b'), "10"), (("11", 'c'), "11")]
    f  = ["10"]

 

とりあえず PDFファイル に書いてあった「例 1」〜「例 3」と「問 4」に対応する dfa を定義してみました。
ghci 上で確認してみたら、思ったように動いてくれているようです。

*Main> dfa1 "aaa"
"Accept"
*Main> dfa1 "aaaa"
"Not Accept"
*Main> dfa2 "ababa"
"Accept"
*Main> dfa2 "abababa"
"Not Accept"
*Main> dfa3 "ababa"
"Accept"
*Main> dfa3 "abababa"
"Not Accept"
*Main> dfa4 "abcacba"
"Accept"
*Main> dfa4 "abcacbacba"
"Not Accept"

 

でも PDFファイル の最後に書いてある「問 5」が未だにわからないんですよね。
御本家に聞いてみようかな?

 

 

HTML generated by org-mode 6.33x in emacs 23

« ブログの内容は鵜呑みにしない方がいいですよ(笑) | トップページ | 素数日を求める »

Haskell」カテゴリの記事

コメント

コメントを書く

コメントは記事投稿者が公開するまで表示されません。

(ウェブ上には掲載しません)

トラックバック

この記事のトラックバックURL:
http://app.cocolog-nifty.com/t/trackback/112020/54396037

この記事へのトラックバック一覧です: オートマトン:

« ブログの内容は鵜呑みにしない方がいいですよ(笑) | トップページ | 素数日を求める »

2016年7月
          1 2
3 4 5 6 7 8 9
10 11 12 13 14 15 16
17 18 19 20 21 22 23
24 25 26 27 28 29 30
31            
フォト

最近のトラックバック

無料ブログはココログ