; dfa ::= (make-dfa (setof state)
;                   (setof letter)
;                   state [element of state]
;                   (letter x state -> state) [letter in sigma, states in states]
;                   state [element of states]
;                   (setof state) [subset of states])
(define-struct dfa (states sigma delta start-state final-states))

; get-delta-hat : dfa -> (state x (listof letter) -> state)
; produces delta-hat, the function that finds the state a dfa is in
; after an arbitrary number of characters has been processed
(define (get-delta-hat dfa)
  (define delta (dfa-delta dfa))
  (define (delta-hat state letters)
    (cond
      [(null? letters) state]
      [else (delta-hat (delta state (car letters)) (cdr letters))]))
  delta-hat)

(define (accepts? dfa str)
  (let ((delta-hat (get-delta-hat dfa)))
    (if (in (delta-hat (dfa-start-state dfa) str) (dfa-final-states dfa))
        #t
        #f)))

(define in member)

(define dfa1 
  (make-dfa
   '(a b c)
   '(a b)
   (lambda (s char)
     (cond
       [(eqv? s 'a)
        (cond 
          [(eqv? char 'a) 'a]
          [(eqv? char 'b) 'b])]
       [(eqv? s 'b)
        (cond
          [(eqv? char 'a) 'a]
          [(eqv? char 'b) 'c])]
       [(eqv? s 'c) 'c]))
   'a
   '(c)))

(accepts? dfa1 '(a b b a))
#t
> (accepts? dfa1 '(a b a))
#f
> (accepts? dfa1 '(a b a b a b a))
#f
> (accepts? dfa1 '(a b a b b a b a))