-
Notifications
You must be signed in to change notification settings - Fork 0
/
Copy pathAutomatonFactory.py
169 lines (130 loc) · 4.74 KB
/
AutomatonFactory.py
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
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
"""
Static Class for generating basic structures for an epsilon-NFA
"""
from Automaton import Automaton
class AutomatonFactory:
"""A static class to create simple, empty, choice, concatenation or star automata.
Construction as seen in https://en.wikipedia.org/wiki/Thompson%27s_construction
IMPORTANT: as described in the article above, every automaton has exactly one final state qf,
which is not co-accessible from any other state.
"""
@staticmethod
def default_automaton(inp):
"""Creates a simple 2-state automaton with a transition on 'inp'
Parameters
----------
inp : str
Transition string or letter.
Returns
-------
Automaton
the created automaton
"""
q = 1
f = 2
a = Automaton()
a.set_start_state(q)
a.add_final_state(f)
a.add_transition(q, f, inp)
return a
@staticmethod
def empty_automaton():
"""Creates a simple 2-state automaton with an empty transition
Returns
-------
Automaton
the created automaton
"""
q = 1
f = 2
a = Automaton()
a.set_start_state(q)
a.add_final_state(f)
a.add_transition(q, f, Automaton.epsilon())
return a
@staticmethod
def choice_automaton(ns: Automaton, nt: Automaton):
"""Creates a choice automaton from two exisiting automata
In Python Regex a choice is represented as a|b
Parameters
----------
ns : Automaton
the first automaton to be merged
nt : Automaton
the second automaton to be merged
Returns
-------
Automaton
the choice automaton
"""
# for a choice automaton the start state of ns is one after q
q = 1
[ns, next_state] = ns.shift_automaton(q + 1)
[nt, f] = nt.shift_automaton(next_state)
union_a = Automaton()
union_a.set_start_state(q)
union_a.add_final_state(f)
union_a.add_transition(q, ns.INIT_STATE, Automaton.epsilon())
union_a.add_transition(q, nt.INIT_STATE, Automaton.epsilon())
union_a.add_transition(ns.FINAL_STATES[0], f, Automaton.epsilon())
union_a.add_transition(nt.FINAL_STATES[0], f, Automaton.epsilon())
# copy transitions from ns and nt respectively
union_a.add_transitions_from_dict(ns.DELTA)
union_a.add_transitions_from_dict(nt.DELTA)
return union_a
@staticmethod
def concat_automaton(ns: Automaton, nt: Automaton):
"""Creates a concatenation automaton from two exisiting automata
In Python Regex a concatenation is represented as ab
Parameters
----------
ns : Automaton
the first automaton to be merged
nt : Automaton
the second automaton to be merged
Returns
-------
Automaton
the concatenation automaton
"""
# for concatenation q and start state of ns are one and the same
q = 1
[ns, next_state] = ns.shift_automaton(q)
# end state of ns and beginning state of nt are merged by having the same state number
[nt, next_state] = nt.shift_automaton(next_state-1)
# next_state is the state that follows N(t), however the last state of N(t) is also f
f = next_state - 1
concat_a = Automaton()
concat_a.set_start_state(q)
concat_a.add_final_state(f)
# concat_a.add_transition(ns.FINAL_STATES[0], nt.INIT_STATE, Automaton.epsilon())
# copy transitions from ns and nt respectively
concat_a.add_transitions_from_dict(ns.DELTA)
concat_a.add_transitions_from_dict(nt.DELTA)
return concat_a
@staticmethod
def star_automaton(ns: Automaton):
"""Creates a star automaton from two exisiting automata
In Python Regex a star is represented as a*
Parameters
----------
ns : Automaton
the automaton to be repeated
Returns
-------
Automaton
the star automaton
"""
# for a star automaton the start state of ns is one after q
q = 1
[ns, f] = ns.shift_automaton(q + 1)
star_a = Automaton()
star_a.set_start_state(q)
star_a.add_final_state(f)
star_a.add_transition(q, ns.INIT_STATE, Automaton.epsilon())
star_a.add_transition(q, f, Automaton.epsilon())
star_a.add_transition(ns.FINAL_STATES[0], f, Automaton.epsilon())
star_a.add_transition(ns.FINAL_STATES[0], ns.INIT_STATE, Automaton.epsilon())
# copy transitions from ns
star_a.add_transitions_from_dict(ns.DELTA)
return star_a