NFAs
Apr 11, 2012 · 1 minute readI saw this a while back and thought it was worth posting. Here’s a complete implementation of NFA (non-deterministic finite automata) in Haskell:
-- Specify the NFA data type
data NFA q s = NFA
{ intialState :: q
, isAccepting :: q -> Bool
, transition :: q -> s -> [q]
}
-- Declare the type of the function test
NFA :: NFA q s -> [s] -> Bool
-- Actual function body test
NFA (NFA i a t) = any a . foldM t i
(Source)