A simple finite automaton

A finite automaton that recognizes the regular language of all strings (made of 0’s and 1’s) that contain the string 001 as a substring. For example, 001, 1001 and 1111001001 are valid in the language, but 11 and 010 are not.

(define (one? x)
  (= x 1))

;; State that skips all 1's.
;; When a 0 is encountered, state changes to q0.
(define (q x)
  (if (one? x)
      q
      q0))

;; If the pattern 00 is seen, moves to state q00.
;; Goes back to q if x = 1.
(define (q0 x)
  (if (one? x)
      q
      q00))

;; State is in the pattern 00.
;; If 1 is seen, move to the end state (e).
;; Otherwise, move back to q0.
(define (q00 x)
   (if (one? x)
       e
       q00))

;; Notifies the state machine that the pattern has been found.
(define (e)
  #t)

;; The state machine itself.
(define (m string)
  (let ((state q))
    (call/ec
      (lambda (k)
        (for x in string
            (set! state (state x))
            (if (eq? state e)
                (k (state))))
       #f))))

Tests:

> (m '(1 1 0 1 0))
#f
> (m '(1 1 0 0 1 0))
#t
> (m '(0 0 1))
#t
> (m '(1 1 1 1 1 1 1 0 0 1 1 1 1 1))
#t