DFA/NFA のテストとして、特定の文字からなるランダムな文字列をテストデータとしたい。例えば、アルファベットが文字 a と b のみからなるDFAに対しては、"a", "ab", "aaaababa" などの文字列を生成したい。 しばらく方法が分からず悩んでいたが以下のよう…

"Regular Expressions and Automata using Haskell" を参考に、データ構造を変更した。具体的にはオートマトンの遷移関数を Haskell の関数にするのを止め、状態遷移の集合とした。 data Labelled a b = Labelled a b a deriving (Eq, Ord) data Epsilon a =…

Haskell の QuickCheck. DFA に対する処理が妥当かどうか、という観点で論理的に満たすべき性質、を書いてみた。最初の関数はユーティリティ。QuickCheck がデフォルトで作ってくれる、ランダムな Int の配列を、特定の DFA のアルファベットの配列に変換し…

いろいろ参考にしながら何とか NFA -> DFA の変換まで書いた。 状態とアルファベットを型変数とできた。また、集合は集合として Data.Set を使った。個人的に満足。 以下のような書き方ができることを知ったのが収穫。これが分からず、MultiParameterTypeCla…