Deterministic & Non-deterministic Finite Automaton

fa.hs

import Data.Set

type State = String
type Alphabet = Char
type Language = String
type States = Set State
type Alphabets = Set Alphabet
type Transition =  State -> Alphabet -> State
type NDTransition =  State -> Alphabet -> States

data FA = DFA States Alphabets Transition State States 
        | NFA States Alphabets NDTransition State States

machine :: FA -> Language -> Bool
machine (DFA states alphabets transition state accepts) [] = member state accepts
machine (DFA states alphabets transition state accepts) (x:xs)
    | notMember x alphabets = False
    | otherwise = machine (DFA states alphabets transition nextState accepts) xs
    where   nextState = transition state x

machine (NFA states alphabets transition state accepts) [] = member state accepts
machine (NFA states alphabets transition state accepts) (x:xs)
    | notMember x alphabets = False
    | otherwise = or $ Prelude.map (\next -> machine (NFA states alphabets transition next accepts) xs ) nextState
    where   nextState   = toList $ union alphabet eta
            alphabet    = transition state x
            eta         = transition state ' '