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