さらに書き換えて、よりDFA,NFA の定義通りにして、よりHaskellらしくできた、つもり。 状態 State 型は型変数を取ることにした。これで文字からなる状態も、状態の対からなる状態も、 Data.Set 、つまり集合からなる状態も、同じように扱える。 同じく、文…

まだなんとなくカッコわるいが、NFA から DFA の変換。 powerSet [] = [[]] powerSet (x:xs) = yss ++ map (x:) yss where yss = powerSet xs subset :: Set.Set State -> Set.Set State subset states = Set.fromList (map (\x -> S'' (Set.fromList x)) (p…

状態の集合をほんとうに集合用のデータ構造 Data.Set を使って書いてみた。 module Fa where import qualified Test.HUnit as Test import qualified Data.Set as Set data State = S String | S' (State, State) | S'' (Set.Set State) deriving (Eq, Show,…

Dfa をさらに書き直してよりエレガント?にした。 状態遷移関数は結局、lookup するだけだった インスタンスを生成するための関数を追加した union をより簡潔に。 module Fa where import qualified Test.HUnit as Test -- import System.Environment data S…

状態の合成を扱えるよう、定義を少し変更して、正規演算の和集合演算を書いてみた。 リスト内包表記だと直積がエレガント。教科書の定義そのままに書ける。まだテストしてないけどとりあえず。 data State = State String | State2 (State, State) deriving …

一度クラスを導入してみたが、あまりにややこしくなってしまった。迷走ぎみだが、シンプルに書き換えた。 module Fa where import System.Environment data State = State String deriving (Eq, Show) type Symbol = Char type Alphabet = [Symbol] -- Dfa s…

さらに考え直して、Transition を無くしてみた。あんまり美しくない気がするが、ほぼ DFA の定義通りだ。 module Fa where import System.Environment data State = State String deriving (Eq, Show) type Symbol = Char type Alphabet = [Symbol] -- Dfa s…

オートマトンの続き。先に書いた例は簡潔だけど、状態遷移関数に相当するものがパターンマッチの中に埋め込まれている。このままでは、オートマトンを新しく定義するためには Eval が必要になる、ように思える。Eval を使うのはたぶん良くない。 しばらく考…