__init__.py 3.69 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
   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

54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
class MutableAutomaton(Automaton):
    def __init__(self):
        super().__init__([], dict())

    def add_state(self, state):
        if state not in super()._states:
            super()._states.append(state)

    def add_transition(self, state, transition):
        if state not in super()._state_to_trans:
            super()._state_to_trans[state] = []
        super()._state_to_trans[state].append(transition)

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

71
72
73
"""An automaton model that generates output"""
class Transducer(Automaton, metaclass=ABCMeta):
    def __init__(self, states, state_to_trans):
74
        super().__init__(states, state_to_trans)
75
76

    @abstractmethod
Paul Fiterau Brostean's avatar
Paul Fiterau Brostean committed
77
    def output(self, trace):
78
79
80
81
82
        pass

"""An automaton model whose states are accepting/rejecting"""
class Acceptor(Automaton, metaclass=ABCMeta):
    def __init__(self, states, state_to_trans, state_to_acc):
83
        super().__init__(states, state_to_trans)
84
        self._state_to_acc = state_to_acc
85
86

    def is_accepting(self, state):
87
        return self._state_to_acc[state]
88
89

    def accepts(self, trace):
90
91
92
        state = self.state(trace)
        is_acc = self.is_accepting(state)
        return is_acc
93

94
95
96
    def __str__(self):
        return str(self._state_to_acc) + "\n" + super().__str__()

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

104
105
106
107
108
    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)
109

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

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