Reworked example from https://www.youtube.com/watch?v=yrf1AYtrKm0

logic-fsm.clj

(ns rel-fsm.core
    (:refer-clojure :exclude [==])
    (:use [clojure.core.logic :exclude [is]] :reload))

(defn logic-fsm-w-mutual-recursion [str out]
  (letfn [(S0 [str out]
              (fresh [r]
                     (conde [(== () str) (== :accept out)]
                            [(resto str r)
                             (conde [(firsto str 0) (S0 r out)]
                                    [(firsto str 1) (S1 r out)])])))
          (S1 [str out]
              (fresh [r]
                     (conde [(== () str) (== :reject out)]
                            [(firsto str 0) (resto str r) (S2 r out)]
                            [(firsto str 1) (resto str r) (S0 r out)])))
          (S2 [str out]
              (fresh [r]
                     (conde [(== () str) (== :reject out)]
                            [(firsto str 0) (resto str r) (S1 r out)]
                            [(firsto str 1) (resto str r) (S2 r out)])))]
    (S0 str out)))

(comment
  (assert (= '([() :accept] [(0) :accept] [(1) :reject] [(0 0) :accept] [(1 0) :reject])
             (run 5 [q] (fresh [str out]
                               (== q [str out])
                               (logic-fsm-w-mutual-recursion str out))))))

(defn logic-fsm []
  (letfn [(S0 [bit out]
                  (matche [bit]
                          ([:end] (== :accept out))
                          ([0] (== S0 out))
                          ([1] (== S1 out))))
          (S1 [bit out]
              (conde [(== :end bit) (== :reject out)]
                     [(== bit 0) (== S2 out)]
                     [(== bit 1) (== S0 out)]))
          (S2 [bit out]
              (conde [(== :end bit) (== :reject out)]
                     [(== bit 0) (== S1 out)]
                     [(== bit 1) (== S2 out)]))
          (invoke [s bit out]
                  (conde
                    [(matche [s]
                             ([S0] (S0 bit out))
                             ([S1] (S1 bit out))
                             ([S2] (S2 bit out))
                             ([:accept] (S0 bit :accept) (S1 bit :accept) (S2 bit :accept))
                             ([:reject] (S0 bit :reject) (S1 bit :reject) (S2 bit :reject)))]
                    [(matche [out]
                             ([:accept] (S0 bit out) (S1 bit out) (S2 bit out))
                             ([:reject] (S0 bit out) (S1 bit out) (S2 bit out))
                             ([:S0] (S0 bit S0) (S1 bit S0) (S2 bit S0))
                             ([:S1] (S0 bit S1) (S1 bit S1) (S2 bit S1))
                             ([:S2] (S0 bit S2) (S1 bit S2) (S2 bit S2)))]))]
    [invoke S0]))

(defn run-fsm [fsm data out]
  (let [[invoke start] (fsm)]
    (letfn [(go [data state]
                (fresh [bit r new-state]
                       (matche [data]
                               ([[]] (invoke state :end out))
                               ([[bit . r]] (invoke state bit new-state)
                                            (go r new-state)))))]
      (go data start))))

(defn trace-fsm-forward [fsm data]
  (let [[-> start-state] (fsm)]
    (reductions
      (fn [state bit]
          (first (run 1 [q]
                      (-> state bit q))))
      start-state
      data)))

(comment
  (run 5 [q] (run-fsm logic-fsm [0 1 1] q))
  (run 20 [str out] (run-fsm logic-fsm str out))
  (clojure.pprint/pprint (trace-fsm-forward logic-fsm [0 1 1 1 0 0 1])))