-
Notifications
You must be signed in to change notification settings - Fork 0
/
Copy pathexamples
149 lines (116 loc) · 4.27 KB
/
examples
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
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
"""DFA
states={'q0', 'q1', 'q2', 'q3', 'q4', 'q5'},
inputs={'0', '1'},
transitions={
'q0': {'0': 'q3', '1': 'q1'},
'q1': {'0': 'q2', '1': 'q5'},
'q2': {'0': 'q2', '1': 'q5'},
'q3': {'0': 'q0', '1': 'q4'},
'q4': {'0': 'q2', '1': 'q5'},
'q5': {'0': 'q5', '1': 'q5'},
},
initial_state='q0',
final_states={'q1', 'q2', 'q4'}
states={'q0', 'q1', 'q2', 'q3', 'q4', 'q5', 'q6', 'q7', 'q8', 'q9'},
inputs={'a', 'b'},
transitions={
'q0': {'a': 'q1', 'b': 'q9'},
'q1': {'a': 'q8', 'b': 'q2'},
'q2': {'a': 'q3', 'b': 'q2'},
'q3': {'a': 'q2', 'b': 'q4'},
'q4': {'a': 'q5', 'b': 'q8'},
'q5': {'a': 'q4', 'b': 'q5'},
'q6': {'a': 'q7', 'b': 'q5'},
'q7': {'a': 'q6', 'b': 'q5'},
'q8': {'a': 'q1', 'b': 'q3'},
'q9': {'a': 'q7', 'b': 'q8'},
},
initial_state='q0',
final_states={'q3', 'q4', 'q9', 'q8'}
states={0, 1, 2, 3, 4, 5, 6, 7, 8, 9},
inputs={'a', 'b'},
transitions={
0: {'a': 1, 'b': 9},
1: {'a': 8, 'b': 2},
2: {'a': 3, 'b': 2},
3: {'a': 2, 'b': 4},
4: {'a': 5, 'b': 8},
5: {'a': 4, 'b': 5},
6: {'a': 7, 'b': 5},
7: {'a': 6, 'b': 5},
8: {'a': 1, 'b': 3},
9: {'a': 7, 'b': 8},
},
initial_state=0,
final_states={3, 4, 9, 8}
states={'q0', 'q1', 'q2', 'q3', 'q4', 'q5'},
inputs={'a', 'b'},
transitions={
'q0': {'a': 'q3', 'b': 'q1'},
'q1': {'a': 'q2', 'b': 'q5'},
'q2': {'a': 'q2', 'b': 'q5'},
'q3': {'a': 'q0', 'b': 'q4'},
'q4': {'a': 'q2', 'b': 'q5'},
'q5': {'a': 'q5', 'b': 'q5'},
},
initial_state='q0',
final_states={'q1', 'q2', 'q4'}
"""
"""NFA
states={'q0', 'q1', 'q2'},
input_symbols={'a', 'b'},
transitions={
'q0': {'a': {'q1'}},
'q1': {'a': {'q1'}, '': {'q2'}},
'q2': {'b': {'q0'}}
},
initial_state='q0',
final_states={'q1'}
states={'q0', 'q1', 'q2'},
input_symbols={'0', '1'},
transitions={
'q0': {'0': {'q0'}, '1': {'q1'},
'q1': {'0': {'q1', 'q2'}, '1': {'q1'}},
'q2': {'0': {'q2'}, '1': {'q1', 'q2'}}
},
initial_state='q0',
final_states={'q2'}
"""
dfa1 = DFA(states={'q0', 'q1', 'q2', 'q3', 'q4', 'q5'},
inputs={'a', 'b'},
transitions={
'q0': {'a': 'q3', 'b': 'q1'},
'q1': {'a': 'q2', 'b': 'q5'},
'q2': {'a': 'q2', 'b': 'q5'},
'q3': {'a': 'q0', 'b': 'q4'},
'q4': {'a': 'q2', 'b': 'q5'},
'q5': {'a': 'q5', 'b': 'q5'},
},
initial_state='q0',
final_states={'q1', 'q2', 'q4'})
dfa2 = DFA(states={'q0', 'q1', 'q2', 'q3', 'q4', 'q5', 'q6', 'q7', 'q8', 'q9'},
inputs={'a', 'b'},
transitions={
'q0': {'a': 'q1', 'b': 'q9'},
'q1': {'a': 'q8', 'b': 'q2'},
'q2': {'a': 'q3', 'b': 'q2'},
'q3': {'a': 'q2', 'b': 'q4'},
'q4': {'a': 'q5', 'b': 'q8'},
'q5': {'a': 'q4', 'b': 'q5'},
'q6': {'a': 'q7', 'b': 'q5'},
'q7': {'a': 'q6', 'b': 'q5'},
'q8': {'a': 'q1', 'b': 'q3'},
'q9': {'a': 'q7', 'b': 'q8'},
},
initial_state='q0',
final_states={'q3', 'q4', 'q9', 'q8'})'''
'''dfa1.union(dfa2)
DFA.union(dfa1, dfa2)
dfa1.intersection(dfa2)
DFA.intersection(dfa1, dfa2)
dfa1.difference(dfa2)
DFA.difference(dfa1, dfa2)
dfa1.is_subset(dfa2)
DFA.is_subset(dfa1, dfa2)
dfa1.is_disjoint(dfa2)
DFA.is_disjoint(dfa1, dfa2)'''