__init__.py 3.71 KB
Newer Older
1
2
3
4
5
6
from abc import ABCMeta, abstractmethod

"""A basic abstract automaton model"""
class Automaton(metaclass=ABCMeta):
   def __init__(self, states, state_to_trans):
      super().__init__()
7
8
      self._states = states
      self._state_to_trans = state_to_trans
9

10
   def start_state(self):
11
      return self._states[0]
12
13

   def states(self):
14
      return list(self._states)
15
16
17

   def transitions(self, state, label=None):
      if label is None:
18
         return list(self._state_to_trans[state])
19
      else:
20
         return list([trans for trans in self._state_to_trans[state] if trans.start_label == label])
21
22

   def state(self, trace):
Paul Fiterau Brostean's avatar
Paul Fiterau Brostean committed
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
       """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]

           # the number of fired transitions can be more than one since we could have multiple equalities
           if len(fired_transitions) == 0:
               raise NoTransitionFired

           if len(fired_transitions) > 1:
               raise MultipleTransitionsFired

           fired_transition = fired_transitions[0]
           crt_state = fired_transition.end_state

       return crt_state
40

41
# Basic __str__ function which works for most FSMs.
42
43
44
45
46
47
48
49
50
   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"

       return str_rep

51
class MutableAutomatonMixin(metaclass=ABCMeta):
52
    def add_state(self, state):
53
54
        if state not in self._states:
            self._states.append(state)
55
56

    def add_transition(self, state, transition):
57
58
59
        if state not in self._state_to_trans:
            self._state_to_trans[state] = []
        self._state_to_trans[state].append(transition)
60
61
62
63

    @abstractmethod
    def to_immutable(self) -> Automaton:
        pass
64

65
66
67
"""An automaton model that generates output"""
class Transducer(Automaton, metaclass=ABCMeta):
    def __init__(self, states, state_to_trans):
68
        super().__init__(states, state_to_trans)
69
70

    @abstractmethod
Paul Fiterau Brostean's avatar
Paul Fiterau Brostean committed
71
    def output(self, trace):
72
73
74
75
76
        pass

"""An automaton model whose states are accepting/rejecting"""
class Acceptor(Automaton, metaclass=ABCMeta):
    def __init__(self, states, state_to_trans, state_to_acc):
77
        super().__init__(states, state_to_trans)
78
        self._state_to_acc = state_to_acc
79
80

    def is_accepting(self, state):
81
        return self._state_to_acc[state]
82
83

    def accepts(self, trace):
84
85
86
        state = self.state(trace)
        is_acc = self.is_accepting(state)
        return is_acc
87

88
89
90
    def __str__(self):
        return str(self._state_to_acc) + "\n" + super().__str__()

91
92
93
94
95
96
97
class MutableAcceptorMixin(MutableAutomatonMixin, metaclass=ABCMeta):
    def add_state(self, state, accepts):
        super().add_state(state)
        self._state_to_acc[state] = accepts



98
"""The most basic transition class available"""
99
100
101
102
class Transition():
    def __init__(self, start_state, start_label, end_state):
        self.start_state = start_state
        self.start_label = start_label
103
        self.end_state = end_state
104

105
106
107
108
109
    def __str__(self, shortened=False):
        if not shortened:
            return "{0} {1} -> {2}".format(self.start_state, self.start_label, self.end_state)
        else:
            "{1} -> {2}".format(self.start_label, self.end_state)
110

111
"""Exception raised when no transition can be fired"""
112
113
114
class NoTransitionFired(Exception):
   pass

115
116
"""Exception raised when several transitions can be fired in a deterministic machine"""
class MultipleTransitionsFired(Exception):
117
    pass