Grundlage des folgenden Codes ist das Video "Endliche Automaten". Der Code ist mit Gambit Scheme getestet worden.
| Kürzel | Bedeutung |
|---|---|
| S | Nichtleere endliche Menge von Zuständen |
| I | Eingabealphabet |
| δ | Übergangsfunktion von S ⨉ I nach S |
| s₀ | Startzustand (Element von S) |
| F | Endzustände (Teilmenge von S) |
Anmerkung: Die folgende Implementation prüft nicht, dass Start- und Endzustände wirklich Zustände sind. Außerdem wird das Eingabealphabet auch nicht verwendet, um die Eingabe zu validieren. Beides passiert implizit in der Übergangsfunktion.
(define (fsm S I δ s₀ F)
(lambda (inputs)
(call/cc (lambda (return)
(define (δ* state inputs)
(if (null? inputs)
(return (if (member state F) #t #f))
(δ* (δ state (car inputs)) (cdr inputs))))
(δ* s₀ inputs)))))(define beispiel-1
(fsm (list 's0 's1 's2 's3)
(list #\0 #\1)
(lambda (state input)
(cond
((equal? state 's0) (cond ((char=? input #\0) 's1)
((char=? input #\1) 's3)
(else #f)))
((equal? state 's1) (cond ((char=? input #\0) 's3)
((char=? input #\1) 's2)
(else #f)))
((equal? state 's2) (cond ((char=? input #\0) 's2)
((char=? input #\1) 's1)
(else #f)))
((equal? state 's3) (cond ((char=? input #\0) 's3)
((char=? input #\1) 's3)
(else #f)))
(else #f)))
's0
(list 's2)))(beispiel-1 (string->list "010")) ; ⇒ #tDa die Parameter S und I nicht verwendet werden, kann man sie auch weglassen und die Übergangsfunktion ans Ende stellen.
(define (fsm* s₀ F δ) (fsm #f #f δ s₀ F))Damit läßt sich das Beispiel für die ganzen Zahlen folgendermaßen schreiben.
(define ganze-zahl
(fsm* 's0 (list 's2 's3)
(lambda (state input)
(cond
((equal? state 's0) (cond ((char=? input #\0) 's3)
((char=? input #\-) 's1)
((char=? input #\1) 's2)
((char=? input #\2) 's2)
((char=? input #\3) 's2)
((char=? input #\4) 's2)
((char=? input #\5) 's2)
((char=? input #\6) 's2)
((char=? input #\7) 's2)
((char=? input #\8) 's2)
((char=? input #\9) 's2)
(else #f)))
((equal? state 's1) (cond ((char=? input #\1) 's2)
((char=? input #\2) 's2)
((char=? input #\3) 's2)
((char=? input #\4) 's2)
((char=? input #\5) 's2)
((char=? input #\6) 's2)
((char=? input #\7) 's2)
((char=? input #\8) 's2)
((char=? input #\9) 's2)
(else #f)))
((equal? state 's2) (cond ((char=? input #\0) 's2)
((char=? input #\1) 's2)
((char=? input #\2) 's2)
((char=? input #\3) 's2)
((char=? input #\4) 's2)
((char=? input #\5) 's2)
((char=? input #\6) 's2)
((char=? input #\7) 's2)
((char=? input #\8) 's2)
((char=? input #\9) 's2)
(else #f)))))))(ganze-zahl (string->list "42")) ; ⇒ #t
(ganze-zahl (string->list "-118")) ; ⇒ #t
(ganze-zahl (string->list "10012")) ; ⇒ #t
(ganze-zahl (string->list "0")) ; ⇒ #t
(ganze-zahl (string->list "007")) ; ⇒ #f