module NFAe
where
import List
import Auxfuns

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

-------------------------------------------------------

eclose :: (Ord q) => [q] -> [[q]] -> (q -> Maybe a -> [q]) -> [q] -> [q]
eclose [] acc d qs = nub $ concat (qs:acc)
eclose _ acc d [] = nub $ concat acc
eclose (_:ind) acc d qs = eclose ind (qs:acc) d (nub $ concat $ [d q Nothing | q <- qs])

eclosure :: (Ord q) => [q] -> (q -> Maybe a -> [q]) -> [q] -> [q]
eclosure bigQ d qs = canonical $ eclose bigQ [] d qs


trace :: (Ord q) => NFAe q s -> [s] -> [[q]]
trace m@(NFAe {states = bigQ, delta = d, start = q0}) w = 
    trace' bigQ d [q0'] q0' w
    where q0' = eclosure bigQ d [q0]
          trace' bigQ d acc qs [] = reverse acc
          trace' bigQ d acc qs (s:ss) = 
              let qs' = eclosure bigQ d $ nub $ concat $ [d q (Just s) | q <- qs]
              in trace' bigQ d (qs':acc) qs' ss

trans :: (Ord q) => [q] -> (q -> Maybe s -> [q]) -> [q] -> [s] -> [q]
trans bigQ d qs [] = qs
trans bigQ d qs (s:ss) = let qs' = eclosure bigQ d $ nub $ concat $ [d q (Just s) | q <- qs]
                    in trans bigQ d qs' ss

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

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

mb = NFAe { states = [0,1,2,3]
         , symbols = "ab"
         , delta = f
         , start = 0
         ,final = [3] }
    where f 0 (Just 'a') = [0,2]
          f 0 Nothing = [1]
          f 1 (Just 'b') = [1,2]
          f 2 (Just 'a') = [3]
          f 3 Nothing = [2]
          f _ _ = []
          
mc = NFAe{ states = [1, 2, 3, 4, 5]
         , symbols = "abcde"
         , delta = f
         , start = 1
         , final = [2] }
  where f 1 (Just 'a') = [2]
        f 1 (Just 'b') = [5]
        f 1 (Just 'd') = [3]
        f 4 (Just 'e') = [4]
        f 5 (Just 'c') = [2]
        f 3 Nothing = [4]
        f 4 Nothing = [2]
        f 5 Nothing = []
        f _ _ = []