Haskell でオートマトン Data.Set + Transition 版

"Regular Expressions and Automata using Haskell" を参考に、データ構造を変更した。具体的にはオートマトンの遷移関数を Haskell の関数にするのを止め、状態遷移の集合とした。

data Labelled a b = Labelled a b a deriving (Eq, Ord)
data Epsilon a = Epsilon a a deriving (Eq, Ord)
data DFA a b = DFA
    (Set a) -- A finite set of states.
    (Set b) -- A finite set of symbol (alphabet).
    (Set (Labelled a b)) -- A set of transition.
    a -- A start state.
    (Set a) -- A set of accept states.
data NFA a b = NFA
    (Set a) -- A finite set of states.
    (Set b) -- A finite set of symbol (alphabet).
    (Set (Labelled a b)) -- A set of transition.
    (Set (Epsilon a)) -- A set of epsilon-transition.
    (Set a) -- A set of start state.
    (Set a) -- A set of accept states.

構造の変更によって、実際にDFAと状態と文字が与えられた際に遷移先を求めるために補助関数 transit1 が必要となった。細かい選択として、

  • 文字による遷移と、ε-遷移は、異なるデータ型とした。
  • NFA は文字による遷移とε-遷移は別の集合として保持することとした。
  • NFA の始状態は状態の集合とした。

前バージョンと比較して、

  • show や、DFA を NFA に変換する操作 convDFAToNFA などが単純化された。
  • 遷移の向きをひっくり返す操作 revDFA, revNFA が単純化された。

で、これらの準備の元、Brzozowski アルゴリズムを用いた DFA/NFA の状態数の最小化はだいたい以下のようになる（※正確には、到達しえない状態を削除する操作が挟まる予定）。

revDFA (DFA qset cset dset q0 fset) = NFA qset cset dset' empty q0set' fset'
    where
      q0set' = fset
      dset' = S.map revTrans dset
      fset' = singleton q0

revNFA (NFA qset cset dset eset q0set fset) = NFA qset cset dset' eset' q0set' fset'
    where
      q0set' = fset
      dset' = S.map revTrans dset
      eset' = S.map revEtrans eset
      fset' = q0set

minimizeDFA fa = (rename' . convNFAToDFA . revDFA . convNFAToDFA . revDFA) fa
minimizeNFA fa = (rename' . convNFAToDFA . revDFA . convNFAToDFA . revNFA) fa

エレガントではないだろうか?

このあとテストをたくさん足す必要あり。

Links