-
Notifications
You must be signed in to change notification settings - Fork 0
/
DFA-machines.rkt
63 lines (56 loc) · 1.72 KB
/
DFA-machines.rkt
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
#lang racket
(define DFA-non-accept
(list
'("a") ; Sigma
'(NA) ; States
'NA ; Start state
'((NA "a" NA)) ; Transitions
'())) ; Final states
(define DFA-accept-empty
(list
'("a") ; Sigma
'(S0 NA) ; States
'S0 ; Start state
'(
(S0 "a" NA)
(NA "a" NA)) ; Transitions
'(S0))) ; Final states
(define DFA-always-accept
(list
'("a") ; Sigma
'(S0) ; States
'S0 ; Start state
'((S0 "a" S0)) ; Transitions
'(S0))) ; Final states
(define DFA-accept-1-char
(list
'("a") ; Sigma
'(S0 S1 NA) ; States
'S0 ; Start state
'(
(S0 "a" S1)
(S1 "a" NA)
(NA "a" NA)) ; Transitions
'(S1))) ; Final states
(define DFA-accept-1-or-more-Bs-no-As
(list
'("a" "b") ; Sigma
'(S0 B NA) ; States
'S0 ; Start state
'(
(S0 "a" NA) (S0 "b" B)
(B "a" NA) (B "b" B)
(NA "a" NA) (NA "b" NA)) ; Transitions
'(B))) ; Final states
(define DFA-accept-alternating
(list
'("a" "b") ; Sigma
'(S0 A B NA) ; States
'S0 ; Start state
'(
(S0 "a" A) (S0 "b" B)
( A "a" NA) ( A "b" B)
( B "a" A) ( B "b" NA)
(NA "a" NA) (NA "b" NA)) ; Transitions
'(S0 A B))) ; Final states
(provide (all-defined-out))