This is a Non-deterministic Finite Automata executor.

afn.lisp

; trans - transition function in the following format
;   '((:s "q0" :c #\a :f "q1") ...)
(defun exec-afn (word stat trans end)
  (if (= 0 (length word))
    (if (remove-if-not #'(lambda (fs) (remove-if-not #'(lambda (s) (string= fs s)) stat)) end)
      (progn (format t "Done! Returned TRUE~%") t)
      (progn (format t "Done! Returned FALSE~%") nil))
    (dolist (s stat)
      (exec-afn (subseq word 1)
                (let ((next-states nil))
                  (dolist (tr (remove-if-not #'(lambda (tr) (char= (getf tr :c) (char word 0)))
                                             (remove-if-not #'(lambda (tr) (string= s (getf tr :s)))
                                                            trans)))
                    (setf next-states (append next-states (list (getf tr :f)))))
                  next-states)
                trans end))))

For an unknown reason, the function keeps returning NIL, instead of returning T in the appropriate cases. Interesting thing is the FORMAT output is correct.