__init__.py 7.53 KB
Newer Older
1
import pprint
2
from abc import ABCMeta, abstractmethod
3
4
from typing import List

Paul Fiterau Brostean's avatar
Paul Fiterau Brostean committed
5
"""The most basic transition class available"""
6
7
8
9
10
11
12
13
14


class Transition():
    def __init__(self, start_state, start_label, end_state):
        self.start_state = start_state
        self.start_label = start_label
        self.end_state = end_state

    def __str__(self, shortened=False):
Paul Fiterau Brostean's avatar
Paul Fiterau Brostean committed
15
        short = "{0} -> {1}".format(self.start_label, self.end_state)
16
        if not shortened:
Paul Fiterau Brostean's avatar
Paul Fiterau Brostean committed
17
            return "{0} {1}".format(self.start_state, short)
18
        else:
Paul Fiterau Brostean's avatar
Paul Fiterau Brostean committed
19
20
            return short

21
22

"""Exception raised when no transition can be fired"""
Paul Fiterau Brostean's avatar
Paul Fiterau Brostean committed
23
24


25
class NoTransitionFired(Exception):
Paul Fiterau Brostean's avatar
Paul Fiterau Brostean committed
26
27
    pass

28
29

"""Exception raised when several transitions can be fired in a deterministic machine"""
Paul Fiterau Brostean's avatar
Paul Fiterau Brostean committed
30
31


32
33
class MultipleTransitionsFired(Exception):
    pass
34

Paul Fiterau Brostean's avatar
Paul Fiterau Brostean committed
35

36
"""A basic abstract automaton model"""
Paul Fiterau Brostean's avatar
Paul Fiterau Brostean committed
37
38


39
class Automaton(metaclass=ABCMeta):
40
    def __init__(self, states, state_to_trans, acc_trans_seq={}):
Paul Fiterau Brostean's avatar
Paul Fiterau Brostean committed
41
42
43
        super().__init__()
        self._states = states
        self._state_to_trans = state_to_trans
44
        self._acc_trans_seq = acc_trans_seq
45

Paul Fiterau Brostean's avatar
Paul Fiterau Brostean committed
46
47
    def start_state(self):
        return self._states[0]
48

49
50
51
    def acc_trans_seq(self, state=None) -> List[Transition]:
        """returns the access sequence to a state in the form of transitions"""
        if state is not None:
52
            return list(self._acc_trans_seq[state])
53
        else:
54
            return dict(self._acc_trans_seq)
55
56
57
58

    def acc_seq(self, state=None):
        """returns the access sequence to a state in the form of sequences of inputs"""
        if state is not None:
59
            if len(self._acc_trans_seq) == 0:
60
                raise Exception("Access sequences haven't been defined for this machine")
61
            return self._seq(self._acc_trans_seq[state])
62
        else:
63
            return {state:self._seq(self._acc_trans_seq[state]) for state in self.states()}
64

Paul Fiterau Brostean's avatar
Paul Fiterau Brostean committed
65
66
    def states(self):
        return list(self._states)
67

Paul Fiterau Brostean's avatar
Paul Fiterau Brostean committed
68
69
70
71
72
    def transitions(self, state, label=None) -> List[Transition]:
        if label is None:
            return list(self._state_to_trans[state])
        else:
            return list([trans for trans in self._state_to_trans[state] if trans.start_label == label])
73

Paul Fiterau Brostean's avatar
Paul Fiterau Brostean committed
74
75
76
77
78
79
    def state(self, trace):
        """state function which also provides a basic implementation"""
        crt_state = self.start_state()
        for symbol in trace:
            transitions = self.transitions(crt_state, symbol)
            fired_transitions = [trans for trans in transitions if trans.start_label == symbol]
Paul Fiterau Brostean's avatar
Paul Fiterau Brostean committed
80

Paul Fiterau Brostean's avatar
Paul Fiterau Brostean committed
81
82
83
            # the number of fired transitions can be more than one since we could have multiple equalities
            if len(fired_transitions) == 0:
                raise NoTransitionFired
Paul Fiterau Brostean's avatar
Paul Fiterau Brostean committed
84

Paul Fiterau Brostean's avatar
Paul Fiterau Brostean committed
85
86
            if len(fired_transitions) > 1:
                raise MultipleTransitionsFired
Paul Fiterau Brostean's avatar
Paul Fiterau Brostean committed
87

Paul Fiterau Brostean's avatar
Paul Fiterau Brostean committed
88
89
            fired_transition = fired_transitions[0]
            crt_state = fired_transition.end_state
Paul Fiterau Brostean's avatar
Paul Fiterau Brostean committed
90

Paul Fiterau Brostean's avatar
Paul Fiterau Brostean committed
91
        return crt_state
92

93
94
95
96
97
    @abstractmethod
    def _seq(self, transitions:List[Transition])->List[object]:
        """returns the sequence of inputs generated by execution of these transitions"""
        pass

98
99
100
    def input_labels(self):
        return set([trans.start_label for trans in self.transitions(self.start_state())])

Paul Fiterau Brostean's avatar
Paul Fiterau Brostean committed
101
102
103
    @abstractmethod
    def output(self, trace):
        pass
104

Paul Fiterau Brostean's avatar
Paul Fiterau Brostean committed
105
106
107
    # Basic __str__ function which works for most FSMs.
    def __str__(self):
        str_rep = ""
108
        str_rep += str(self._acc_trans_seq) + "\n"
Paul Fiterau Brostean's avatar
Paul Fiterau Brostean committed
109
110
111
112
        for state in self.states():
            str_rep += str(state) + "\n"
            for tran in self.transitions(state):
                str_rep += "\t" + tran.__str__(shortened=True) + "\n"
113

Paul Fiterau Brostean's avatar
Paul Fiterau Brostean committed
114
        return str_rep
115

116
class MutableAutomatonMixin(metaclass=ABCMeta):
117
    def add_state(self:Automaton, state):
118
119
        if state not in self._states:
            self._states.append(state)
120

121
    def add_transition(self:Automaton, state, transition):
122
123
124
        if state not in self._state_to_trans:
            self._state_to_trans[state] = []
        self._state_to_trans[state].append(transition)
125

126
127
128
129
130
131
132
133
134
135
    def generate_acc_seq(self:Automaton):
        """generates access sequences for an automaton. It optionally takes in old access sequences, which are """
        new_acc_seq = dict()
        ptree = get_prefix_tree(self)
        for state in self.states():
            pred = lambda x: (x.state == state)
            node = ptree.find_node(pred)
            if node is None:
                raise Exception("Could not find state {0} in tree {1}".format(state, ptree))
            new_acc_seq[state] = node.path()
136
        assert(len(new_acc_seq) == len(self.states()))
137
138
        pprint.pprint(new_acc_seq)
        self._acc_trans_seq = new_acc_seq
139

140
141
142
    @abstractmethod
    def to_immutable(self) -> Automaton:
        pass
143

Paul Fiterau Brostean's avatar
Paul Fiterau Brostean committed
144

145
"""An automaton model that generates output"""
Paul Fiterau Brostean's avatar
Paul Fiterau Brostean committed
146
147


148
class Transducer(Automaton, metaclass=ABCMeta):
149
150
    def __init__(self, states, state_to_trans, acc_trans_seq={}):
        super().__init__(states, state_to_trans, acc_trans_seq)
151
152

    @abstractmethod
Paul Fiterau Brostean's avatar
Paul Fiterau Brostean committed
153
    def output(self, trace):
154
155
        pass

156

Paul Fiterau Brostean's avatar
Paul Fiterau Brostean committed
157

158
"""An automaton model whose states are accepting/rejecting"""
Paul Fiterau Brostean's avatar
Paul Fiterau Brostean committed
159
160


161
class Acceptor(Automaton, metaclass=ABCMeta):
162
163
    def __init__(self, states, state_to_trans, state_to_acc, acc_trans_seq={}):
        super().__init__(states, state_to_trans, acc_trans_seq)
164
        self._state_to_acc = state_to_acc
165
166

    def is_accepting(self, state):
167
        return self._state_to_acc[state]
168
169

    def accepts(self, trace):
170
171
172
        state = self.state(trace)
        is_acc = self.is_accepting(state)
        return is_acc
173

174
175
176
    def output(self, trace):
        self.accepts(trace)

177
178
179
    def __str__(self):
        return str(self._state_to_acc) + "\n" + super().__str__()

Paul Fiterau Brostean's avatar
Paul Fiterau Brostean committed
180

181
182
183
184
class MutableAcceptorMixin(MutableAutomatonMixin, metaclass=ABCMeta):
    def add_state(self, state, accepts):
        super().add_state(state)
        self._state_to_acc[state] = accepts
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199


def get_prefix_tree(aut : Automaton):
    visited  = set()
    to_visit = set()
    root = PrefixTree(aut.start_state())
    to_visit.add(root)
    while len(to_visit) > 0:
        crt_node = to_visit.pop()
        visited.add(crt_node.state)
        transitions = aut.transitions(crt_node.state)
        for trans in transitions:
            if trans.end_state not in visited:
                child_node = PrefixTree(trans.end_state)
                crt_node.add_child(trans, child_node)
200
                to_visit.add(child_node)
201
202
203
204
205
206
207
    return root


class PrefixTree():
    def __init__(self, state):
        self.state = state
        self.tr_tree:dict = {}
208
        self.parent:PrefixTree = None
209
210
211
212
213

    def add_child(self, trans, tree):
        self.tr_tree[trans] = tree
        self.tr_tree[trans].parent = self

214
215
216
217
218
219
220
221
222
223
224
225
226
    def path(self) -> List[Transition]:
        if self.parent is None:
            return []
        else:
            for (tr, node) in self.parent.tr_tree.items():
                if node is self:
                    return self.parent.path()+[tr]
            raise Exception("Miscontructed tree")

    def find_node(self, predicate):
        if predicate(self):
            return self
        elif len(self.tr_tree) == 0:
227
228
229
            return None
        else:
            for (tran, child) in self.tr_tree.items():
230
231
232
233
234
235
236
237
238
239
240
241
                node = child.find_node(predicate)
                if node is not None:
                    return node
            return None

    def __str__(self, tabs=0):
        space = "".join(["\t" for _ in range(0, tabs)])
        tree = "(n_{0}".format(self.state)
        for (tr, node) in self.tr_tree.items():
            tree += "\n" + space + " {0} -> {1}".format(tr, node.__str__(tabs=tabs + 1))
        tree += ")"
        return tree