__init__.py 3.21 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
40
41
42
       """state function which also provides a basic implementation"""
       crt_state = self.start_state()
       tr_str = crt_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
           tr_str += " {0} {1}".format(symbol, crt_state)

       # print(tr_str)
       return crt_state
43

44
# Basic __str__ function which works for most FSMs.
45
46
47
48
49
50
51
52
53
54
   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


55
56
57
"""An automaton model that generates output"""
class Transducer(Automaton, metaclass=ABCMeta):
    def __init__(self, states, state_to_trans):
58
        super().__init__(states, state_to_trans)
59
60

    @abstractmethod
Paul Fiterau Brostean's avatar
Paul Fiterau Brostean committed
61
    def output(self, trace):
62
63
64
65
66
        pass

"""An automaton model whose states are accepting/rejecting"""
class Acceptor(Automaton, metaclass=ABCMeta):
    def __init__(self, states, state_to_trans, state_to_acc):
67
        super().__init__(states, state_to_trans)
68
        self._state_to_acc = state_to_acc
69
70

    def is_accepting(self, state):
71
        return self._state_to_acc[state]
72
73

    def accepts(self, trace):
74
75
76
        state = self.state(trace)
        is_acc = self.is_accepting(state)
        return is_acc
77

78
79
80
    def __str__(self):
        return str(self._state_to_acc) + "\n" + super().__str__()

81
"""The most basic transition class available"""
82
83
84
85
class Transition():
    def __init__(self, start_state, start_label, end_state):
        self.start_state = start_state
        self.start_label = start_label
86
        self.end_state = end_state
87

88
89
90
91
92
    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)
93

94
"""Exception raised when no transition can be fired"""
95
96
97
class NoTransitionFired(Exception):
   pass

98
99
"""Exception raised when several transitions can be fired in a deterministic machine"""
class MultipleTransitionsFired(Exception):
100
101
    pass