;; deterministic finite acceptor
(defclass dfa ()
  ((state-list :initform nil
	       :initarg :sl
	       :type 'list
	       :accessor state-list
	       :allocation :instance)  
   (initial-state :initform nil
		  :initarg :is
		  :accessor initial-state
		  :type 'dfa-state
		  :allocation :instance)
   (alphabet-list :type 'list
		  :initform nil
		  :initarg :alphabet-list
		  :accessor alphabets
		  :allocation :instance)
   (final-states :initform nil
		 :initarg :final-states
		 :type 'list
		 :accessor final-states
		 :allocation :instance))
  (:documentation "improve documentation!"))

(defclass dfa-state ()
  ((input-nextstate-output-list
    :initform nil
    :initarg :ino
    :type 'list
    :accessor get-states
    :allocation :instance
    :documentation "derp")
   (name
    :initform ""
    :initarg :state-name
    :type 'string
    :accessor state-name
    :allocation :instance
    :documentation
    "name of the state"))
  (:documentation "nerp"))

(defmethod dfa-accept? ((machine dfa) str)
  (let* ((current (initial-state machine))
	 (alpha (alphabets machine))
	 (acceptable t)
	 (next-name)
	 (next)
	 (pos)
	 (len 0))
    (do ((i 0 (incf i)))
	((or (>= i (length str))
	     (not (member (read-from-string (string (elt str i))) alpha)))
	 (setf len i))
      (setf pos (position
		   (read-from-string (string (elt str i))) alpha))
      (if current (setf next-name (elt (get-states current) pos)))
      (setf next (find (symbol-name next-name) (state-list foo) :test #'(lambda (x y) (string= x (state-name y)))))
      (setf current next))
    (if (and acceptable
	     next
	     (>= len (length str))
	     (member (read-from-string (state-name next)) (final-states machine) :test #'string=))
	t nil)))

(defun in-alphabet? (c alpha)
  (format t "c: ~A~%alpha: ~A~%" c alpha)
  (member c alpha :test #'(lambda (x y)
			    (string= x (symbol-name y)))))

(defun state-table->dfa (table)
  (let* ((alphabet (car table))
	 (states (cdr table))
	 (st-list nil)
	 (dee-eff-aye (make-instance 'dfa :alphabet-list alphabet)))
    (dolist (st states)
      (format t "(car st): ~A~%" (car st))
      (let ((temp-state (make-instance 'dfa-state
				       :state-name (symbol-name (car st))))
	    (temp-lst nil))
	(format t "state-name: ~A~%" (symbol-name (car st)))
	(format t "(cdr st) : ~A~%" (cdr st))
	(dolist (st (cdr st))
	  (push st temp-lst))
	(format t "temp-list: ~A~%" temp-lst)
	(setf (get-states temp-state)  (reverse temp-lst))
	(format t "fuck yer face~%")
	(push temp-state st-list)))
      (setf (state-list dee-eff-aye) (reverse st-list))
      dee-eff-aye))

;; SAMPLE USAGE 
(setf foo (state-table->dfa
	   ;; table for accepting a+b+
	   '(    (a   b)
	     (q0 q1   nil)
	     (q1 q1  q2)
	     (q2 nil q2))))
(setf (initial-state foo) (car (state-list foo)))
(push "Q2" (final-states foo))