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))))