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