-- Work by: IMPORTANT! PUT YOUR NAME(S) AND MATRIC NUMBER(S) HERE!

import List

type FSM q = ([q], Alphabet, q, [q], [Transition q])
type Alphabet = [Char]
type Transition q = (q, Char, q)

m1 :: FSM Int
m1 = ([0,1,2,3,4],
      ['a','b'],
      0,
      [4],
      [(0,'a',1), (0,'b',1), (0,'a',2), (0,'b',2),
       (1,'b',4), (2,'a',3), (2,'b',3), (3,'b',4),
       (4,'a',4), (4,'b',4)])

m2 :: FSM Char
m2 = (['A','B','C','D'],
      ['0','1'],
      'B',
      ['A','B','C'],
      [('A', '0', 'D'), ('A', '1', 'B'),
       ('B', '0', 'A'), ('B', '1', 'C'),
       ('C', '0', 'B'), ('C', '1', 'D'),
       ('D', '0', 'D'), ('D', '1', 'D')])

states :: FSM q -> [q]
alph ::  FSM q -> Alphabet
start ::  FSM q -> q
final ::  FSM q -> [q]
trans ::  FSM q -> [Transition q]

states (u,a,s,f,t) = u
alph (u,a,s,f,t) = a
start (u,a,s,f,t) = s
final (u,a,s,f,t) = f
trans (u,a,s,f,t) = t

delta  :: (Eq q) => FSM q -> q -> Char -> [q]
delta m q x = [ c | (a,b,c) <- (trans m) , a == q && b == x]

accepts :: (Eq q) => FSM q -> String -> Bool
accepts m xs = acc m (start m) xs

acc :: (Eq q) => FSM q -> q -> String -> Bool
acc m q []     = q `elem` (final m)
acc m q (x:xs) = True `elem` [acc m y xs | y <- (delta m q x) ]

canonical :: (Ord q) => [q] -> [q]
canonical q = List.sort ( List.nub  q)

ddelta :: (Ord q) => FSM q -> [q] -> Char -> [q]
ddelta m qs x = concat (canonical [ delta m q x | q <- qs ])

next :: (Ord q) => FSM q -> [[q]] -> [[q]]
next m qs = List.nub ( qs ++ [ ddelta m q a | q <- qs , a <- (alph m)])


reachable :: (Ord q) => FSM q -> [[q]] -> [[q]]
reachable  = undefined

dfinal :: (Ord q) => FSM q -> [[q]] -> [[q]]
dfinal = undefined

dtrans :: (Ord q) => FSM q -> [[q]] -> [Transition [q]]
dtrans = undefined

deterministic :: (Ord q) => FSM q -> FSM [q]
deterministic = undefined