;;; using fsa's for matching and generation

(define (fsa-match fsa seq)
  (let match? ((state (fsa-start-state fsa))
	       (input seq))
    (if (null? input) (state-in? state (fsa-goal-states fsa))
      (any (lambda (state) (match? state (cdr input)))
	   (fsa-state-successors fsa state (car input))))))

;; TODO fsa-generate and fsa-generate-next

(define (fsa-generate fsa max-length)
  (let gen ((state (fsa-start-state fsa))
	    (prefix '()))
    (if (< max-length (length prefix)) '()
      (let ((subs (append-map
		    (lambda (trans)
		      (append-map
			(lambda (inp) (gen (transition-destination trans)
					   (cons inp prefix)))
			(transition-lexicon trans)))
		    (fsa-transitions-from fsa (list state)))))
	(if (not (state-in? state (fsa-goal-states fsa))) subs
	  (cons (reverse prefix) subs))))))