Back to NotesOctober12Proj
;; FSM simulator (deterministic) ;; Katie Rivard, Oct 12 2004 ;; construct an fsm -- use standard order <{Q}, {E}, d, S, {F}> ;; each input is a list ;; construct delta using [make-empty-delta] and [delta-add] ;; WARNING: does NOT use robustness checking to make sure your delta, S, F, Q, and E agree! (define (make-fsm states alphabet delta start-state accept-states) (list states alphabet delta start-state accept-states)) ;; unpack elements of the fsm (define (get-states fsm) (car fsm)) ;; list (define (get-alphabet fsm) (cadr fsm)) ;; list (define (get-delta fsm) (caddr fsm)) ;; delta structure (define (get-start-state fsm) (caar (cdddr fsm))) ;; symbol (define (get-accept-states fsm) (cadr (cdddr fsm))) ;; list ;; construct a delta function (define (make-empty-delta) '()) (define (delta-add from-st symb to-st delta) (cons (list from-st symb to-st) delta)) ;; unpack elements of delta for the top transition in the list (define (cur-from-st delta) (caar delta)) (define (cur-symb delta) (cadar delta)) (define (cur-to-st delta) (caddar delta)) ;; grab the next state given the current state and the input symbol ;; WARNING: if two different valid transitions are in the delta, ;; (ie, you tried to make a nondeterministic fsm) ;; the first transition encountered/last entered into the delta will be taken! (define (delta-resolve from-st symb delta) (if (null? delta) 'FAIL (if (and (eq? from-st (cur-from-st delta)) (eq? symb (cur-symb delta))) (cur-to-st delta) (delta-resolve from-st symb (cdr delta))))) ;; returns #t if state is an accept state, #f otherwise (define (is-accept-state st accept-states) (if (null? accept-states) #f (if (eq? st (car accept-states)) #t (is-accept-state st (cdr accept-states))))) ;; returns whether the fsm accepts the string or not (define (run-fsm fsm str) (iterate-fsm (get-start-state fsm) fsm str)) (define (iterate-fsm curstate fsm str) (display curstate) (newline) ;; visual (if (null? str) ;; @end of input -- should be in an accept state (is-accept-state curstate (get-accept-states fsm)) (iterate-fsm (delta-resolve curstate (car str) (get-delta fsm)) fsm (cdr str))))