The constructor for an FSM requires the programmer to specify the starting state, the set of transitions, and a set of accepting states. The transitions are represented by triple of the form (s, i, t), which is interpreted as if the machine is in state s with i as the next input, then it should transition to state t. To run the simulator on a machine M with input inp, one invokes the accept function with the encoding of machine M and inp as parameters. Please write the encoding of a DFSM called eAoB that accepts all strings that contain an even number of as or an odd number of bs

your program file start with comments and the following: module Submission where

import DFSM import

Data.Set (Set)

import qualified Data.Set as Set

You will need the imports of Set to use functions like Set.singleton.

module DFSM where

import Data.Set (Set) -- imports Set constructor for type

import qualified Data.Set as Set

{-implementation of arbitrary deterministic FSM.

For simplicity, all states are just integers. This

implementation is more complex than the simple example because the transition function is not hard coded into the program. I.e. the new program can simulate any FSM. Now when we make a transition, we must not just return the new state, but also carry along the transition function and the accepting states. -}

Main program can be run by typing

accept myDFSM inputString

where myDFSM is a description of a deterministic FSM and inputString is the input. The result is a boolean reflecting whether inputString is accepted or not.

{- nextState converts a collection of triples into a transition

function that determines next state from current state and input

Each triple is of the form (s,a,t) where there is transition from s to t on input a. Thus

nextState trans currentState input

returns the state the machine will be in using the transition

function trans after reading input starting from currentState

-}

nextState :: Eq st => [(st, Char, st)] -> st -> Char -> st

-- if no triple applies then throw exception

nextState [] curState letter = error ("no transition on "++[letter])

-- if find matching triple with curState and input, return associated

-- new state from the triple, otherwise keep looking

nextState ((s0,inp,s1):rest) curState input =

if (curState == s0 && input == inp)

then s1

else nextState rest curState input

{- A finite state machine consists of the start state,

the transition function, and the set of accepting states.

-}

data DFSM state = DFSM

{ startState :: state

, transitionFunction :: state -> Char -> state

, acceptingStates :: Set state

}

makeDFSM

:: Eq state => state -> [(state, Char, state)] -> Set state -> DFSM state

makeDFSM start transTriples acceptStates =

DFSM{ startState = start,

transitionFunction = nextState transTriples,

acceptingStates = acceptStates

}

{- gaccept fsm state input returns true iff the fsmm starting in state

goes into an accepting state in fsm.acceptingStates

after reading in all input.

-}

gAccept :: Ord st => DFSM st -> st -> [Char] -> Bool

-- if no input left, see if state in accepting state of fsm

gAccept fsm s [] = Set.member s (acceptingStates fsm)

-- to process next input, find new state from input,

-- and then run fsm on rest of input

gAccept fsm s (fst:rest) = gAccept fsm s' rest where

s' = (transitionFunction fsm) s fst

-- main function to determine if string accepted by fsm.

-- It differs from gAccept in that it automatically starts in official start state of fsm.

accept :: Ord state => DFSM state -> [Char] -> Bool

accept fsm input = gAccept fsm (startState fsm) input

------------ CODE TO TEST IMPLEMENTATION --------------

-- sample transition function corresponding to same machine used

-- in SimpleExampleDFSM.hs earlier

sampleTransitions = [(0,'a',1),(0,'b',2),(1,'a',2),

(1,'b',0),(2,'a',0),(2,'b',2)]

-- complete DDFSM corresponding to machine above

-- try it out by typing: accept sampleDFSM "abaabbb"

sampleDFSM = makeDFSM 0 sampleTransitions (Set.singleton 2)

-- Transition function for DDFSM accepting strings containing aab.

tran2 = [(0,'a',1),(0,'b',0),(1,'a',2),

(1,'b',0),(2,'a',2),(2,'b',3),(3,'a',3),(3,'b',3)]

aabDFSM = makeDFSM 0 tran2 (Set.singleton 3)

please write code in Haskell. This is how you start the file:

have your program file start with comments and the following:

module Submission where

import DFSM

import Data.Set (Set)

import qualified Data.Set as Set

You will need the imports of Set to use functions like Set.singleton

I included the picture of the code below. there are also comments describing each function above.

Essentially you need to write the encoding of a DFSM called eAoB that accepts all strings that contain an even number of a's or and off number of b's

nextState :: Eq st > (st, Char, st)) -> st - Char -> st nextState [] curState letter - error ("no transition on "++[letter]) nextState ((se, inp,si):rest) curstate input = if (curstate...so..inputmine) then si else nextState rest curstate input data DFSM state = DFSM { startState :: state , transitionFunction :: state -> Char -> state . acceptingStates :: Set state 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 makeDFSM :: Eq state -> state -> [(state, Char, state)] -> Set state -> DFSM state makeDFSM start transTriples acceptStates - DFSM{ startState = start, transitionFunction = nextstate transTriples, acceptingStates - acceptStates } gAccept :: Ord st - DFSM st -> st -> (Char) - Bool gAccept fsms () - Set.member s (acceptingStates fsm) gAccept tsm s (fst:rest) = gAccept tsm s' rest where s' = (transitionFunction (sm) s fst accept :: Ord state => DFSM state -> (Char) -> Bool accept tsm input.Accept tsm (startState Ism) Input CODE TO TEST IMPLEMENTA CON sampleTransitions : [(Integer, Char, Integer)) | sampleTransitions : ((Integer, Char, Integer)) | sampleTransltions = ((Integer, Char, Integer)) sampleTransitions = [(@, 'a',1),(0, 'b',2), (1, 'a',2), TIL (1,'b',C),(2, 'a',), (2, 'b',2)) complete DDFSM corresponding to machine above try it out by typing: accept sampleDFSM "abaabbb" sampleDFSM 1 DFSM Integer sampleDFSM HOFSM Integer sampleDFSM :: DFSM Integer sampleDFSM = makeDFSM @ sampleTransitions (set.singleton 2) tran2 :: [linteger, Char, Integer tran2 :: [(Integer, Char, Integer)) tran2 :: [(Integer, Char, Integer)) tran2 = [(@, 'a',1),(0, 'b',C),(1, 'a',2), IT (1,'b',0), (2, 'a', 2), (2, 'b',3), (3, 'a',3), (3, 'b',3)] 59 60 61 62 63 64 65 66 aabDFSM :: DFSM Integer sabOFSM : DFSM Integer | BbDFSM DFSM Integer aabDFSM = makeDFSM @ tran2 (Set. Singleton 3) 67 68 nextState :: Eq st > (st, Char, st)) -> st - Char -> st nextState [] curState letter - error ("no transition on "++[letter]) nextState ((se, inp,si):rest) curstate input = if (curstate...so..inputmine) then si else nextState rest curstate input data DFSM state = DFSM { startState :: state , transitionFunction :: state -> Char -> state . acceptingStates :: Set state 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 makeDFSM :: Eq state -> state -> [(state, Char, state)] -> Set state -> DFSM state makeDFSM start transTriples acceptStates - DFSM{ startState = start, transitionFunction = nextstate transTriples, acceptingStates - acceptStates } gAccept :: Ord st - DFSM st -> st -> (Char) - Bool gAccept fsms () - Set.member s (acceptingStates fsm) gAccept tsm s (fst:rest) = gAccept tsm s' rest where s' = (transitionFunction (sm) s fst accept :: Ord state => DFSM state -> (Char) -> Bool accept tsm input.Accept tsm (startState Ism) Input CODE TO TEST IMPLEMENTA CON sampleTransitions : [(Integer, Char, Integer)) | sampleTransitions : ((Integer, Char, Integer)) | sampleTransltions = ((Integer, Char, Integer)) sampleTransitions = [(@, 'a',1),(0, 'b',2), (1, 'a',2), TIL (1,'b',C),(2, 'a',), (2, 'b',2)) complete DDFSM corresponding to machine above try it out by typing: accept sampleDFSM "abaabbb" sampleDFSM 1 DFSM Integer sampleDFSM HOFSM Integer sampleDFSM :: DFSM Integer sampleDFSM = makeDFSM @ sampleTransitions (set.singleton 2) tran2 :: [linteger, Char, Integer tran2 :: [(Integer, Char, Integer)) tran2 :: [(Integer, Char, Integer)) tran2 = [(@, 'a',1),(0, 'b',C),(1, 'a',2), IT (1,'b',0), (2, 'a', 2), (2, 'b',3), (3, 'a',3), (3, 'b',3)] 59 60 61 62 63 64 65 66 aabDFSM :: DFSM Integer sabOFSM : DFSM Integer | BbDFSM DFSM Integer aabDFSM = makeDFSM @ tran2 (Set. Singleton 3) 67 68