import Data.List (intersect,union)

-- Definition of the types of Deterministic and 
-- Nondeterministic Finite Automata

-- Parameters: q type of states
--             sigma alphabet (type of symbols)

-- Components: transition function, 
--             initial state(s), 
--             accepting states

data DFA q sigma = DFA (q -> sigma -> q) q [q]
data NFA q sigma = NFA (q -> sigma -> [q]) [q] [q]

deltaDFA :: DFA q sigma -> q -> sigma -> q
deltaDFA (DFA delta _ _) = delta

initialDFA :: DFA q sigma -> q
initialDFA (DFA _ q0 _) = q0

finalDFA :: DFA q sigma -> [q]
finalDFA (DFA _ _ fs) = fs

deltaNFA :: NFA q sigma -> q -> sigma -> [q]
deltaNFA (NFA delta _ _) = delta

initialNFA :: NFA q sigma -> [q]
initialNFA (NFA _ q0s _) = q0s

finalNFA :: NFA q sigma -> [q]
finalNFA (NFA _ _ fs) = fs


-- EXAMPLES

data Qex = Qex0 | Qex1 | Qex2 deriving (Eq,Enum,Bounded,Show)
data Sigma = A | B    deriving Show

dfa0 :: DFA Qex Sigma
dfa0 = DFA delta Qex0 [Qex0]
  where
    delta Qex0 A = Qex1
    delta Qex0 B = Qex0
    delta Qex1 A = Qex2
    delta Qex1 B = Qex1
    delta Qex2 A = Qex0
    delta Qex2 B = Qex2

nfa0 :: NFA Qex Sigma
nfa0 = NFA delta [Qex0] [Qex1,Qex2]
  where
    delta Qex0 A = [Qex0]
    delta Qex0 B = [Qex0,Qex1]
    delta Qex1 _ = [Qex2]
    delta Qex2 _ = []
    
-- Exercise 1: draw diagrams for the DFA dfa0 and the NFA nfa0

-- Exercise 2: define a DFA accepting words in which 
--   As and Bs have the same parity

-- Exercise 3: define an NFA accepting words containing
--   the substring ABBA
 
-- AUXILIARY FUNCTIONS

-- Represent a finite set as a list
-- Given a finite set, compute the set of its subsets
powerset :: [a] -> [[a]]
powerset [] = [[]]
powerset (a:as) = powerset as ++ map (a:) (powerset as)

-- Compute the list of all elements of a bounded type
--   We will use it to get the list of all states
allStates:: (Enum q, Bounded q) => [q]
allStates = [minBound..maxBound]

-- Union of all elements is a set of sets
-- union of two sets/lists is predefined
unions :: Eq a => [[a]] -> [a]
unions = foldl union []

-- Extended transition function for a DFA
-- (starDFA dfa q w) gives the state that we reach
--   after dfa processes the word w starting in state q

starDFA :: Eq q => DFA q sigma -> q -> [sigma] -> q
-- Exercise 4

-- Run a DFA on a word and determine if it accepts it or not

runDFA :: Eq q => DFA q sigma -> [sigma] -> Bool
-- Exercise 5

-- Extended transition function for an NFA

starNFA :: Eq q => NFA q sigma -> [q] -> [sigma] -> [q]
-- Exercise 6

-- Accepting subsets of states of an NFA
--  (acceptsNFA nfa qs) is True if one of the states
--  in qs is accepting. 

acceptsNFA :: Eq q => NFA q sigma -> [q] -> Bool
-- Exercise 7

-- Determine if a word is accepted by an NFA

runNFA :: Eq q => NFA q sigma -> [sigma] -> Bool
-- Exercise 8

-- Trasform a DFA into an NFA (trivial)

dfa2nfa :: DFA q sigma -> NFA q sigma
-- Exercise 9

-- Transform an NFA into a DFA
--   The subset construction

nfa2dfa :: (Eq q, Enum q, Bounded q) => NFA q sigma -> DFA [q] sigma
-- Exercise 10
    
-- Exercise 11
--  Instead of using a type parameter for the alphabet
--  we could give it as an argument of the types DFA and NFA
--  as a list of symbols (that is, a string)
--  Modify the whole file to use this representation