(defconstant +dfa2+
  '((ALPHABET        (a b))
    (STATES          (1 2 3 4))
    (INITIAL-STATE   1)
    (FINAL-STATES    (4))
    (TRANSITIONS     ((1 a 2) (1 b 5)   
  		      (2 a 4) (2 b 3)   
  		      (3 a 5) (3 b 2)   
  		      (4 a 5) (4 b 5)   
  		      (5 a 5) (5 b 5))))
  "A deterministic finite-state automaton that accepts the language
   {a b^n a, n is an even number}, i.e. {aa, abba, abbbba, ...}."
)

(defun finalp (state dfa)
  "Returns non-null value if state is among the final states of the dfa."
  (member state (second (assoc 'FINAL-STATES dfa))))

(defun transition (current-state symbol dfa)
  "Returns the state you get to when you take a transition on symbol
   starting from current-state in the dfa.  Because this is a DETERMINISTIC
   finite-state automaton, it is guaranteed that there is exactly one such
   value for every pairing of current-state and symbol, i.e. the find-if
   will never return nil.
  "
  (let ((all-transitions (second (assoc 'TRANSITIONS dfa))))
    (third (find-if #'(lambda (triple)  
			(and (equal (first triple)  current-state)
			     (equal (second triple) symbol)))
		    all-transitions))))

(defun accepts (input dfa)
  "Input is a list of symbols from the alphabet of the automaton.
   This function returns true if the dfa winds up in a final 
   state after going through the entire input, nil otherwise. 
  "
  (let ((initial-state (second (assoc 'INITIAL-STATE dfa))))
    (and (accepts-from-current input initial-state dfa) t)))

(defun accepts-from-current (input current-state dfa)
  "If input has been exhausted, return true if current state is a final state.
   Otherwise, take the transition from current-state based on the first
    symbol in the input, and see whether the automaton accepts the
    new input (which is one symbol shorter) starting from the state
    you end up in.
  "
  (cond ((null input) 
	 (finalp current-state dfa))
	(t 
	 (accepts-from-current (rest input)
			       (transition current-state (first input) dfa)
			       dfa))))