dfa-regex-check.rkt

#lang racket

(require racket/generator)

(define (M input)
  (define (q0 input)
    (match input
      [(list) #f]
      [(list 0 xs ...) (q1 xs)]
      [(list 1 xs ...) (q0 xs)]))
  (define (q1 input)
    (match input
      [(list) #f]
      [(list 0 xs ...) (q0 xs)]
      [(list 1 xs ...) (q2 xs)]))
  (define (q2 input)
    (match input
      [(list) #f]
      [(list 0 xs ...) (q3 xs)]
      [(list 1 xs ...) (q0 xs)]))
  (define (q3 input)
    (match input
      [(list) #f]
      [(list 0 xs ...) (q1 xs)]
      [(list 1 xs ...) (q4 xs)]))
  (define (q4 input)
    (match input
      [(list) #f]
      [(list 0 xs ...) (q1 xs)]
      [(list 1 xs ...) (q5 xs)]))
  (define (q5 input)
    (match input
      [(list) #t]
      [(list 0 xs ...) (q1 xs)]
      [(list 1 xs ...) (q0 xs)]))
  (q0 input))






(define rx #px"^[01]*01011$")

(define (check input)
  (printf "Checking ~a\n" input)
  (define s (string-append* (map number->string input)))
  (when (xor (regexp-match rx s) (M input))
    (yield input)))

(define failures
  (in-generator
   (let loop ([input '()] [depth 10])
     (when (> depth 0)
       (check input)
       (loop (cons 0 input) (sub1 depth))
       (loop (cons 1 input) (sub1 depth))))))


(define the-failures (sequence->list failures))

(printf "Inputs where DFA disagrees with regex\n")

(for ([failure the-failures])
  (printf "~a\n" failure))