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