**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 ABCthreeA = 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 ABCabcs = 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 ABCaborba = 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…