module NFA 
where
import List
import Auxfuns

data NFA q s = NFA { states :: [q],
                     symbols :: [s],
                     delta :: q -> s -> [q],
                     start :: q,
                     final :: [q]}

trans :: (Ord q) => (q -> s -> [q]) -> [q] -> [s] -> [q]
trans d qs [] = qs
trans d qs (s:ss) = let qs' = unions $ [d q s | q <- qs]
                    in trans d qs' ss

accept :: (Ord q) => NFA q s -> [s] -> Bool
accept m@(NFA {delta = d, start = q0, final = f}) w
    = not $ null $ intersect (trans d [q0] w) f

ma = NFA { states = q,
           symbols = sigma,
           delta = \p a -> [(2*p+a) `mod` 3],
           start = 0,
           final = [1]
         }
    where q = [0..2]
          sigma = [0,1]

mb :: NFA Int Char          
mb = NFA { states = [0,1,2]
         , symbols = ['a','b']
         , delta = f
         , start = 0
         , final = [1] }
     where f 0 'a' = [1]
           f 0 'b' = [2]
           f 1 _   = [1]
           f 2 _   = [2]
           
mc = NFA { states = [0,1,2,3]
         , symbols = "ab"
         , delta = f
         , start = 0
         ,final = [3] }
    where f 0 'a' = [1]
          f 1 'a' = [2]
          f 1 'b' = [1]
          f 2 'b' = [3,1]
          f 2 'a' = [2]
          f _ _ = []