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

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


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
14
        short = "{0} -> {1}".format(self.start_label, self.end_state)
15
        if not shortened:
Paul Fiterau Brostean's avatar
Paul Fiterau Brostean committed
16
            return "{0} {1}".format(self.start_state, short)
17
        else:
Paul Fiterau Brostean's avatar
Paul Fiterau Brostean committed
18
19
            return short

20
21

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


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

27
28

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


31
32
class MultipleTransitionsFired(Exception):
    pass
33

Paul Fiterau Brostean's avatar
Paul Fiterau Brostean committed
34

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


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

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

48
49
50
    def acc_seq(self, state):
        return self._acc_seq[state]

Paul Fiterau Brostean's avatar
Paul Fiterau Brostean committed
51
52
    def states(self):
        return list(self._states)
53

Paul Fiterau Brostean's avatar
Paul Fiterau Brostean committed
54
55
56
57
58
    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])
59

Paul Fiterau Brostean's avatar
Paul Fiterau Brostean committed
60
61
62
63
64
65
    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
66

Paul Fiterau Brostean's avatar
Paul Fiterau Brostean committed
67
68
69
            # 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
70

Paul Fiterau Brostean's avatar
Paul Fiterau Brostean committed
71
72
            if len(fired_transitions) > 1:
                raise MultipleTransitionsFired
Paul Fiterau Brostean's avatar
Paul Fiterau Brostean committed
73

Paul Fiterau Brostean's avatar
Paul Fiterau Brostean committed
74
75
            fired_transition = fired_transitions[0]
            crt_state = fired_transition.end_state
Paul Fiterau Brostean's avatar
Paul Fiterau Brostean committed
76

Paul Fiterau Brostean's avatar
Paul Fiterau Brostean committed
77
        return crt_state
78

79
80
81
    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
82
83
84
    @abstractmethod
    def output(self, trace):
        pass
85

Paul Fiterau Brostean's avatar
Paul Fiterau Brostean committed
86
87
88
89
90
91
92
    # Basic __str__ function which works for most FSMs.
    def __str__(self):
        str_rep = ""
        for state in self.states():
            str_rep += str(state) + "\n"
            for tran in self.transitions(state):
                str_rep += "\t" + tran.__str__(shortened=True) + "\n"
93

Paul Fiterau Brostean's avatar
Paul Fiterau Brostean committed
94
        return str_rep
95

96
class MutableAutomatonMixin(metaclass=ABCMeta):
97
    def add_state(self, state):
98
99
        if state not in self._states:
            self._states.append(state)
100
101

    def add_transition(self, state, transition):
102
103
104
        if state not in self._state_to_trans:
            self._state_to_trans[state] = []
        self._state_to_trans[state].append(transition)
105

106
107
108
    def add_acc_seq(self, state, trace):
        self._acc_seq[state] = trace

109
110
111
    @abstractmethod
    def to_immutable(self) -> Automaton:
        pass
112

Paul Fiterau Brostean's avatar
Paul Fiterau Brostean committed
113

114
"""An automaton model that generates output"""
Paul Fiterau Brostean's avatar
Paul Fiterau Brostean committed
115
116


117
118
class Transducer(Automaton, metaclass=ABCMeta):
    def __init__(self, states, state_to_trans):
119
        super().__init__(states, state_to_trans)
120
121

    @abstractmethod
Paul Fiterau Brostean's avatar
Paul Fiterau Brostean committed
122
    def output(self, trace):
123
124
        pass

125
126
127
128
    def output_labels(self):
        return set([trans.output for state in self.states() for trans in self.transitions(state)])


Paul Fiterau Brostean's avatar
Paul Fiterau Brostean committed
129

130
"""An automaton model whose states are accepting/rejecting"""
Paul Fiterau Brostean's avatar
Paul Fiterau Brostean committed
131
132


133
134
class Acceptor(Automaton, metaclass=ABCMeta):
    def __init__(self, states, state_to_trans, state_to_acc):
135
        super().__init__(states, state_to_trans)
136
        self._state_to_acc = state_to_acc
137
138

    def is_accepting(self, state):
139
        return self._state_to_acc[state]
140
141

    def accepts(self, trace):
142
143
144
        state = self.state(trace)
        is_acc = self.is_accepting(state)
        return is_acc
145

146
147
148
    def output(self, trace):
        self.accepts(trace)

149
150
151
    def __str__(self):
        return str(self._state_to_acc) + "\n" + super().__str__()

Paul Fiterau Brostean's avatar
Paul Fiterau Brostean committed
152

153
154
155
156
class MutableAcceptorMixin(MutableAutomatonMixin, metaclass=ABCMeta):
    def add_state(self, state, accepts):
        super().add_state(state)
        self._state_to_acc[state] = accepts
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205


def get_acc_seq(aut : Automaton, runner, old_acc_seq = dict()):
    new_acc_seq = {aut.state(acc_seq):acc_seq for acc_seq in old_acc_seq.values()}
    not_covered = [state for state in aut.states() if state not in new_acc_seq.keys()]
    ptree = get_prefix_tree(aut)
    for state in not_covered:
        trace = runner(ptree.path(state))
        new_acc_seq[state] = trace
    return new_acc_seq


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)
    return root




class PrefixTree():
    def __init__(self, state):
        self.state = state
        self.tr_tree:dict = {}
        self.parent = None

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

    def path(self, state) -> List[Transition]:
        if len(self.tr_tree):
            return None
        else:
            for (tran, child) in self.tr_tree.items():
                path = child.path(state)
                if path is not None:
                    return [tran] + path
            return None