write in HASKELL
module Project4 where
import Control.Monad
— In this project, you will give some DFAs as values in the DFAtype defined
— below. Note that this type differs slightly from the one definedin class,
— because the transition function may return Nothing, to indicatethe absence
— of a transition (i.e., that the machine will transition to animplicit
— failure state for that combination of state and input).
data DFA state symbol = DFA
{ alphabet :: [symbol]
, states :: [state]
, initial :: state
, transit :: state -> symbol -> Maybe state
, accept :: state -> Bool
}
— This version of accepts uses foldM to halt processing of theinput string
— when the DFA transitions to the failure state. For our purposes,we have
—
— foldM :: (b -> a -> Maybe b) -> b -> [a] -> Maybeb
—
— foldM will use the transition function to process the inputstring until
— it exhausts the string or the transition function returnsNothing.
—
— The function maybe :: b -> (a -> b) -> Maybe a -> ballows us to apply
— a function to the result of foldM, or return a default valuewhen foldM
— returns Nothing.
accepts :: DFA state symbol -> [symbol] -> Bool
accepts dfa = maybe False (accept dfa) . foldM (transit dfa)(initial dfa)
— For example:
data ABC = A | B | C deriving (Show, Eq, Ord)
— A DFA for the language over {A,B,C} containing strings whereA occurs
— exactly once.
oneA :: DFA Int ABC
oneA = DFA
{ alphabet = [A,B,C]
, states = [0,1]
, initial = 0
, transit = delta
, accept = (== 1)
}
where
delta 0 A = Just 1
delta 0 _ = Just 0
delta 1 A = Nothing
delta 1 _ = Just 1
— A DFA for the language over {A,B,C} containing strings where Aoccurs
— exactly three times.
—
— > accepts threeA [A,B,A,A]
— True
threeA :: DFA Int ABC
threeA = undefined
— A DFA for the language over {A,B,C} where every non-final Ais followed by
— B, every non-final B is followed by C, and every non-final C isfollowed by
— A.
—
— > accepts abcs [B,C,A,B,C,A,B]
— True
— > accepts abcs []
— True
— > accepts abcs [A,B,B,C]
— False
abcs :: DFA Int ABC
abcs = undefined
— A DFA for the language over {A,B,C} of strings containing atleast one of the
— sequences “AB” or “BA”.
—
— > accepts aborba [C,B,C,A,B,C,C,A]
— True
— > accepts aborba [A,A,A,A,B]
— True
— > accepts aborba [A,C,C,B,C,A]
— False
aborba :: DFA Int ABC
aborba = undefined
Expert Answer
Answer to write in HASKELL module Project4 where import Control.Monad — In this project, you will give some DFAs as values in the…