A deterministic finite automaton (DFA) is an abstract machine that recognizes a regular language. Usually a DFA is defined by a 5-tuple, but instead we'll use a map with 5 keys:

• :states is the set of states for the DFA.
• :alphabet is the set of symbols included in the language recognized by the DFA.
• :start is the start state of the DFA.
• :accepts is the set of accept states in the DFA.
• :transitions is the transition function for the DFA, mapping :states ⨯ :alphabet onto :states.

Write a function that takes as input a DFA definition (as described above) and returns a sequence enumerating all strings in the language recognized by the DFA. Note: Although the DFA itself is finite and only recognizes finite-length strings it can still recognize an infinite set of finite-length strings. And because stack space is finite, make sure you don't get stuck in an infinite loop that's not producing results every so often!

jafingerhut's solution:

;; Maintain a map step-n-states where the keys are all states ;; reachable by some input string of exactly length n, and the value ;; for each state is the set of all strings of length n that lead to ;; that state.

;; Initially the map contains {(:start dfa) #{""}}. That is, the only ;; reachable state for a length 0 string is the start state, and only ;; the empty string leads to it. That is always the starting state ;; when n=0.

;; One function will take such a map and the DFA, and return a new map ;; for n+1, i.e. all states reachable by a string of length 1 more ;; than the current map.

;; Stop if the map becomes empty, i.e. no states are reachable for a ;; string of the given length. That will only happen for DFAs that ;; accept a finite set of strings. Many DFAs accept an infinite set ;; of strings.

;; At each step, concatenate the lists of strings reachable by states ;; that are accepting, if any, with the lazily computed list of longer ;; strings accepted.

(ns live.test
  (:require [cljs.test :refer-macros [deftest is run-tests]]))
  
(defn dfa [m]
  (let [transitions (m :transitions)
        accepts (m :accepts)
        next-step-n-states
        (fn [step-n-states]
          (apply merge-with concat
                 (for [q (keys step-n-states)
                       [next-symbol next-state] (transitions q)]
                   {next-state (vec (map #(str % next-symbol)
                                         (step-n-states q)))})))
        f (fn f [step-n-states]
            (let [states (keys step-n-states)]
              (if (not= 0 (count states))
                (concat (mapcat step-n-states (filter accepts states))
                        (lazy-seq (f (next-step-n-states step-n-states)))))))]
    (f {(:start m) [""]})))
    
(deftest dfa-test
  (is (= #{"a" "ab" "abc"}
   (set (dfa '{:states #{q0 q1 q2 q3}
              :alphabet #{a b c}
              :start q0
              :accepts #{q1 q2 q3}
              :transitions {q0 {a q1}
                            q1 {b q2}
                            q2 {c q3}}}))))
  (is (= #{"hi" "hey" "hello"}
   (set (dfa '{:states #{q0 q1 q2 q3 q4 q5 q6 q7}
              :alphabet #{e h i l o y}
              :start q0
              :accepts #{q2 q4 q7}
              :transitions {q0 {h q1}
                            q1 {i q2, e q3}
                            q3 {l q5, y q4}
                            q5 {l q6}
                            q6 {o q7}}}))))
  (is (= (set (let [ss "vwxyz"] (for [i ss, j ss, k ss, l ss] (str i j k l))))
   (set (dfa '{:states #{q0 q1 q2 q3 q4}
              :alphabet #{v w x y z}
              :start q0
              :accepts #{q4}
              :transitions {q0 {v q1, w q1, x q1, y q1, z q1}
                            q1 {v q2, w q2, x q2, y q2, z q2}
                            q2 {v q3, w q3, x q3, y q3, z q3}
                            q3 {v q4, w q4, x q4, y q4, z q4}}}))))
  (is (let [res (take 2000 (dfa '{:states #{q0 q1}
                           :alphabet #{0 1}
                           :start q0
                           :accepts #{q0}
                           :transitions {q0 {0 q0, 1 q1}
                                         q1 {0 q1, 1 q0}}}))]
  (and (every? (partial re-matches #"0*(?:10*10*)*") res)
       (= res (distinct res)))))
  (is (let [res (take 2000 (dfa '{:states #{q0 q1}
                           :alphabet #{n m}
                           :start q0
                           :accepts #{q1}
                           :transitions {q0 {n q0, m q1}}}))]
  (and (every? (partial re-matches #"n*m") res)
       (= res (distinct res)))))
  (is (let [res (take 2000 (dfa '{:states #{q0 q1 q2 q3 q4 q5 q6 q7 q8 q9}
                           :alphabet #{i l o m p t}
                           :start q0
                           :accepts #{q5 q8}
                           :transitions {q0 {l q1}
                                         q1 {i q2, o q6}
                                         q2 {m q3}
                                         q3 {i q4}
                                         q4 {t q5}
                                         q6 {o q7}
                                         q7 {p q8}
                                         q8 {l q9}
                                         q9 {o q6}}}))]
  (and (every? (partial re-matches #"limit|(?:loop)+") res)
       (= res (distinct res))))))
       
(run-tests)