Using Dr Racket...

Finite State Machines poses a problem concerning finite state machines and strings but immediately defers to this chapter because the solution calls for generative recursion. You have now acquired the design knowledge needed to tackle the problem.

Design the function fsm-match. It consumes the data representation of a finite state machine and a string. It produces #true if the sequence of characters in the string causes the finite state machine to transition from an initial state to a final state.

(define-struct transition [current key next]) (define-struct fsm [initial transitions final]) ; An FSM is a structure: ; A 1Transition is a structure: ; An FSM-State is String. ; data example: see exercise 109 (define fsm-a-bc*-d (make-fsm FSM-State [List-of 1Transition] FSM-State) (make-transition FSM-State 1String FSM-State) (make-fsm (list (make-transition (make-transition "BC" "b" "BC" (make-transition "BC" "c" "BC") (make-transition "BC" "d" "DD") "AA" "a" "BC") (define-struct transition [current key next]) (define-struct fsm [initial transitions final]) ; An FSM is a structure: ; A 1Transition is a structure: ; An FSM-State is String. ; data example: see exercise 109 (define fsm-a-bc*-d (make-fsm FSM-State [List-of 1Transition] FSM-State) (make-transition FSM-State 1String FSM-State) (make-fsm (list (make-transition (make-transition "BC" "b" "BC" (make-transition "BC" "c" "BC") (make-transition "BC" "d" "DD") "AA" "a" "BC")