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")) ; ⇒ #t
Da 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