                                             cap-hist)))
            valid-trans))))))
 
+(defn accepts?
+  "Takes a description of a PDA and a string, returns true if the PDA accepts
+  the string and false otherwise."
+  [pda s]
+  (-> (parse pda s #{})
+      first
+      true?))
 
 (defn extract [s parts]
   "Takes a string and a collection of three tuples of the form [name start

                 ; make a q1 -> q1 transtion poping the same symbol from stack
                 ; and input for every terminal symbol.
                 :q1 (concat q1
                             (map (fn [x] [:q1 x x :ε]) 
                                  (mset/difference (set (coll-flatten Σ))
                                                   (set (keys (:prod-rules cfg)))
                                                   #{:ε})))

  (:require
    (clojure [string :as string]
             [set :as mset])))

(def alpha (set (map char (concat (range 65 91) (range 97 123)))))

(def paren-balancer
  "A PDA that accepts any string with balanced paren pairs."
