This module adds support for finite state machines, automata and transducers. See class FiniteStateMachine and the examples below for details creating one.
We can easily create a finite state machine by
sage: fsm = FiniteStateMachine()
sage: fsm
Finite state machine with 0 states
By default this is the empty finite state machine, so not very interesting. Let’s create some states and transitions:
sage: from sage.combinat.finite_state_machine import FSMState, FSMTransition
sage: day = FSMState('day')
sage: night = FSMState('night')
sage: sunrise = FSMTransition(night, day)
sage: sunset = FSMTransition(day, night)
And now let’s add those states and transitions to our finite state machine:
sage: fsm.add_transition(sunrise)
Transition from 'night' to 'day': -|-
sage: fsm.add_transition(sunset)
Transition from 'day' to 'night': -|-
Note that the states are added automatically, since they are present in the transitions. We could add the states manually by
sage: fsm.add_state(day)
'day'
sage: fsm.add_state(night)
'night'
Anyhow, we got the following finite state machine:
sage: fsm
Finite state machine with 2 states
We can also visualize it as a graph by
sage: fsm.graph()
Digraph on 2 vertices
Alternatively, we could have created the finite state machine above simply by
sage: FiniteStateMachine([('night', 'day'), ('day', 'night')])
Finite state machine with 2 states
or by
sage: fsm = FiniteStateMachine()
sage: day = fsm.add_state('day')
sage: night = fsm.add_state('night')
sage: sunrise = fsm.add_transition(night, day)
sage: sunset = fsm.add_transition(day, night)
sage: fsm
Finite state machine with 2 states
We want to build an automaton which recognizes non-adjacent forms (NAFs), i.e., sequences which have no adjacent non-zeros. We use \(0\), \(1\), and \(-1\) as digits:
sage: NAF = Automaton(
....: {'A': [('A', 0), ('B', 1), ('B', -1)], 'B': [('A', 0)]})
sage: NAF.state('A').is_initial = True
sage: NAF.state('A').is_final = True
sage: NAF.state('B').is_final = True
sage: NAF
Automaton with 2 states
Of course, we could have specified the initial and final states directly in the definition of NAF by initial_states=['A'] and final_states=['A', 'B'].
So let’s test the automaton with some input:
sage: NAF([0])[0]
True
sage: NAF([0, 1])[0]
True
sage: NAF([1, -1])[0]
False
sage: NAF([0, -1, 0, 1])[0]
True
sage: NAF([0, -1, -1, -1, 0])[0]
False
sage: NAF([-1, 0, 0, 1, 1])[0]
False
Alternatively, we could call that by
sage: NAF.process([-1, 0, 0, 1, 1])[0]
False
Let’s build a simple transducer, which rewrites a binary word by iverting each bit:
sage: inverter = Transducer({'A': [('A', 0, 1), ('A', 1, 0)]},
....: initial_states=['A'], final_states=['A'])
We can look at the states and transitions:
sage: inverter.states()
['A']
sage: for t in inverter.transitions():
....: print t
Transition from 'A' to 'A': 0|1
Transition from 'A' to 'A': 1|0
Now we apply a word to it and see what the transducer does:
sage: inverter([0, 1, 0, 0, 1, 1, 0, 0, 0, 1, 1, 1])
(True, 'A', [1, 0, 1, 1, 0, 0, 1, 1, 1, 0, 0, 0])
True means, that we landed in a final state, that state is labeled 'A', and we also got an output.
Now we build a transducer, which divides a binary number by 3. The labels of the states are the remainder of the division. The transition function is
sage: def f(state_from, read):
....: if state_from + read <= 1:
....: state_to = 2*state_from + read
....: write = 0
....: else:
....: state_to = 2*state_from + read - 3
....: write = 1
....: return (state_to, write)
We get the transducer with
sage: D = Transducer(f, initial_states=[0], final_states=[0],
....: input_alphabet=[0, 1])
Now we want to divide 13 by 3:
sage: D([1, 1, 0, 1])
(False, 1, [0, 1, 0, 0])
So we have 13 : 3 = 4 and the reminder is 1. False means 13 is not divisible by 3.
Let’s use the previous example “divison by \(3\)” to demonstrate the optional state and transition parameters hook.
First, we define, what those functions should do. In our case, this is just saying in which state we are and which transition we take
sage: def state_hook(state, process):
....: print "We are now in State %s." % (state.label(),)
sage: from sage.combinat.finite_state_machine import FSMWordSymbol
sage: def transition_hook(transition, process):
....: print ("Currently we go from %s to %s, "
....: "reading %s and writing %s." % (
....: transition.from_state, transition.to_state,
....: FSMWordSymbol(transition.word_in),
....: FSMWordSymbol(transition.word_out)))
Now, let’s add these hook-functions to the existing transducer:
sage: for s in D.iter_states():
....: s.hook = state_hook
sage: for t in D.iter_transitions():
....: t.hook = transition_hook
Rerunning the process again now gives the following output:
sage: D.process([1, 1, 0, 1])
We are now in State 0.
Currently we go from 0 to 1, reading 1 and writing 0.
We are now in State 1.
Currently we go from 1 to 0, reading 1 and writing 1.
We are now in State 0.
Currently we go from 0 to 0, reading 0 and writing 0.
We are now in State 0.
Currently we go from 0 to 1, reading 1 and writing 0.
We are now in State 1.
(False, 1, [0, 1, 0, 0])
The example above just explains the basic idea of using hook-functions. In the following, we will use those hooks more seriously.
Suppose we have a binary input and want to accept all sequences with the same number of \(0\) and \(1\). This cannot be done with a finite automaton. Anyhow, we can make usage of the hook functions to extend our finite automaton by a counter:
sage: from sage.combinat.finite_state_machine import FSMState, FSMTransition
sage: C = Automaton()
sage: def update_counter(state, process):
....: l = process.read_letter()
....: process.fsm.counter += 1 if l == 1 else -1
....: if process.fsm.counter > 0:
....: next_state = 'positive'
....: elif process.fsm.counter < 0:
....: next_state = 'negative'
....: else:
....: next_state = 'zero'
....: return FSMTransition(state, process.fsm.state(next_state),
....: l, process.fsm.counter)
sage: C.add_state(FSMState('zero', hook=update_counter,
....: is_initial=True, is_final=True))
'zero'
sage: C.add_state(FSMState('positive', hook=update_counter))
'positive'
sage: C.add_state(FSMState('negative', hook=update_counter))
'negative'
Now, let’s input some sequence:
sage: C.counter = 0; C([1, 1, 1, 1, 0, 0])
(False, 'positive', [1, 2, 3, 4, 3, 2])
The result is False, since there are four \(1\) but only two \(0\). We land in the state positive and we can also see the values of the counter in each step.
Let’s try some other examples:
sage: C.counter = 0; C([1, 1, 0, 0])
(True, 'zero', [1, 2, 1, 0])
sage: C.counter = 0; C([0, 1, 0, 0])
(False, 'negative', [-1, 0, -1, -2])
AUTHORS:
Daniel Krenn (2012-03-27): initial version
Clemens Heuberger (2012-04-05): initial version
Sara Kropf (2012-04-17): initial version
Clemens Heuberger (2013-08-21): release candidate for Sage patch
Daniel Krenn (2013-08-21): release candidate for Sage patch
Sara Kropf (2013-08-21): release candidate for Sage patch
Clemens Heuberger (2013-09-02): documentation improved
Daniel Krenn (2013-09-13): comments from trac worked in
product, composition, etc. changed (for consistency), representation of state changed, documentation improved
Daniel Krenn (2013-11-04): whitespaces in documentation corrected
Clemens Heuberger (2013-11-04): full_group_by added
Daniel Krenn (2013-11-04): next release candidate for Sage patch
Sara Kropf (2013-11-08): fix for adjacency matrix
Clemens Heuberger (2013-11-11): fix for prepone_output
docstring of FiniteStateMachine rewritten, Automaton and Transducer inherited from FiniteStateMachine
comments from trac 15078
ACKNOWLEDGEMENT:
Bases: sage.combinat.finite_state_machine.FiniteStateMachine
This creates an automaton, which is a finite state machine, whose transitions have input labels.
An automaton has additional features like creating a deterministic and a minimized automaton.
See class FiniteStateMachine for more information.
EXAMPLES:
We can create an automaton recognizing even numbers (given in binary and read from left to right) in the following way:
sage: A = Automaton([('P', 'Q', 0), ('P', 'P', 1),
....: ('Q', 'P', 1), ('Q', 'Q', 0)],
....: initial_states=['P'], final_states=['Q'])
sage: A
Automaton with 2 states
sage: A([0])[0]
True
sage: A([1,1,0])[0]
True
sage: A([1,0,1])[0]
False
Note that the full output of the commands above gives more information and looks like this:
sage: A([1,0,1])
(False, 'P', [])
TESTS:
sage: Automaton()
Automaton with 0 states
Returns a deterministic automaton which accepts the same input words as the original one.
INPUT:
Nothing.
OUTPUT:
A new automaton, which is deterministic.
The labels of the states of the new automaton are frozensets of states of self.
The input alphabet must be specified. It is restricted to nice cases: input words have to have length at most \(1\).
EXAMPLES:
sage: aut = Automaton([('A', 'A', 0), ('A', 'B', 1), ('B', 'B', 1)],
....: initial_states=['A'], final_states=['B'])
sage: aut.determinisation().transitions()
[Transition from frozenset(['A'])
to frozenset(['A']): 0|-,
Transition from frozenset(['A'])
to frozenset(['B']): 1|-,
Transition from frozenset(['B'])
to frozenset([]): 0|-,
Transition from frozenset(['B'])
to frozenset(['B']): 1|-,
Transition from frozenset([])
to frozenset([]): 0|-,
Transition from frozenset([])
to frozenset([]): 1|-]
sage: A = Automaton([('A', 'A', 1), ('A', 'A', 0), ('A', 'B', 1),
....: ('B', 'C', 0), ('C', 'C', 1), ('C', 'C', 0)],
....: initial_states=['A'], final_states=['C'])
sage: A.determinisation().states()
[frozenset(['A']), frozenset(['A', 'B']),
frozenset(['A', 'C']), frozenset(['A', 'C', 'B'])]
TESTS:
This is from #15078, comment 13.
sage: D = {'A': [('A', 'a'), ('B', 'a'), ('A', 'b')],
....: 'C': [], 'B': [('C', 'b')]}
sage: auto = Automaton(D, initial_states=['A'], final_states=['C'])
sage: auto.is_deterministic()
False
sage: auto.process(list('aaab'))
(False, 'A', [])
sage: auto.states()
['A', 'C', 'B']
sage: auto.determinisation()
Automaton with 3 states
Returns the minimization of the input automaton as a new automaton.
INPUT:
OUTPUT:
A new automaton.
The resulting automaton is deterministic and has a minimal number of states.
EXAMPLES:
sage: A = Automaton([('A', 'A', 1), ('A', 'A', 0), ('A', 'B', 1),
....: ('B', 'C', 0), ('C', 'C', 1), ('C', 'C', 0)],
....: initial_states=['A'], final_states=['C'])
sage: B = A.minimization(algorithm='Brzozowski')
sage: B.transitions(B.states()[1])
[Transition from frozenset([frozenset(['A', 'C', 'B']),
frozenset(['C', 'B']), frozenset(['A', 'C'])]) to
frozenset([frozenset(['A', 'C', 'B']), frozenset(['C', 'B']),
frozenset(['A', 'C']), frozenset(['C'])]): 0|-,
Transition from frozenset([frozenset(['A', 'C', 'B']),
frozenset(['C', 'B']), frozenset(['A', 'C'])]) to
frozenset([frozenset(['A', 'C', 'B']), frozenset(['C', 'B']),
frozenset(['A', 'C'])]): 1|-]
sage: len(B.states())
3
sage: C = A.minimization(algorithm='Brzozowski')
sage: C.transitions(C.states()[1])
[Transition from frozenset([frozenset(['A', 'C', 'B']),
frozenset(['C', 'B']), frozenset(['A', 'C'])]) to
frozenset([frozenset(['A', 'C', 'B']), frozenset(['C', 'B']),
frozenset(['A', 'C']), frozenset(['C'])]): 0|-,
Transition from frozenset([frozenset(['A', 'C', 'B']),
frozenset(['C', 'B']), frozenset(['A', 'C'])]) to
frozenset([frozenset(['A', 'C', 'B']), frozenset(['C', 'B']),
frozenset(['A', 'C'])]): 1|-]
sage: len(C.states())
3
sage: aut = Automaton([('1', '2', 'a'), ('2', '3', 'b'),
....: ('3', '2', 'a'), ('2', '1', 'b'),
....: ('3', '4', 'a'), ('4', '3', 'b')],
....: initial_states=['1'], final_states=['1'])
sage: min = aut.minimization(algorithm='Brzozowski')
sage: [len(min.states()), len(aut.states())]
[3, 4]
sage: min = aut.minimization(algorithm='Moore')
Traceback (most recent call last):
...
NotImplementedError: Minimization via Moore's Algorithm is only
implemented for deterministic finite state machines
Returns a string associated to the input letter.
INPUT:
OUTPUT:
If letter is None the symbol for the empty word FSMEmptyWordSymbol is returned, otherwise the string associated to the letter.
EXAMPLES:
sage: from sage.combinat.finite_state_machine import FSMLetterSymbol
sage: FSMLetterSymbol(0)
'0'
sage: FSMLetterSymbol(None)
'-'
This class is for processing an input string on a finite state machine.
An instance of this class is generated when FiniteStateMachine.process() or FiniteStateMachine.iter_process() of the finite state machine is invoked. It behaves like an iterator which, in each step, takes one letter of the input and runs (one step on) the finite state machine with this input. More precisely, in each step, the process iterator takes an outgoing transition of the current state, whose input label equals the input letter of the tape. The output label of the transition, if present, is written on the output tape.
INPUT:
The process (iteration) stops if there are no more input letters on the tape. In this case a StopIteration exception is thrown. As result the following attributes are available:
Current values of those attribtes (except accept_input) are (also) available during the iteration.
OUTPUT:
An iterator.
EXAMPLES:
The following transducer reads binary words and outputs a word, where blocks of ones are replaced by just a single one. Further only words that end with a zero are accepted.
sage: T = Transducer({'A': [('A', 0, 0), ('B', 1, None)],
....: 'B': [('B', 1, None), ('A', 0, [1, 0])]},
....: initial_states=['A'], final_states=['A'])
sage: input = [1, 1, 0, 0, 1, 0, 1, 1, 1, 0]
sage: T.process(input)
(True, 'A', [1, 0, 0, 1, 0, 1, 0])
The function FiniteStateMachine.process() created a new FSMProcessIterator. We can do that manually, too, and get full access to the iteration process:
sage: from sage.combinat.finite_state_machine import FSMProcessIterator
sage: it = FSMProcessIterator(T, input_tape=input)
sage: for _ in it:
....: print (it.current_state, it.output_tape)
('B', [])
('B', [])
('A', [1, 0])
('A', [1, 0, 0])
('B', [1, 0, 0])
('A', [1, 0, 0, 1, 0])
('B', [1, 0, 0, 1, 0])
('B', [1, 0, 0, 1, 0])
('B', [1, 0, 0, 1, 0])
('A', [1, 0, 0, 1, 0, 1, 0])
sage: it.accept_input
True
Returns the next transition according to word_in. It is assumed that we are in state self.current_state.
INPUT:
OUTPUT:
The next transition according to word_in. It is assumed that we are in state self.current_state.
EXAMPLES:
sage: from sage.combinat.finite_state_machine import FSMProcessIterator
sage: inverter = Transducer({'A': [('A', 0, 1), ('A', 1, 0)]},
....: initial_states=['A'], final_states=['A'])
sage: it = FSMProcessIterator(inverter, input_tape=[0, 1])
sage: it.get_next_transition([0])
Transition from 'A' to 'A': 0|1
Makes one step in processing the input tape.
INPUT:
Nothing.
OUTPUT:
It returns the taken transition. A StopIteration exception is thrown when there is nothing more to read.
EXAMPLES:
sage: from sage.combinat.finite_state_machine import FSMProcessIterator
sage: inverter = Transducer({'A': [('A', 0, 1), ('A', 1, 0)]},
....: initial_states=['A'], final_states=['A'])
sage: it = FSMProcessIterator(inverter, input_tape=[0, 1])
sage: it.next()
Transition from 'A' to 'A': 0|1
sage: it.next()
Transition from 'A' to 'A': 1|0
sage: it.next()
Traceback (most recent call last):
...
StopIteration
Reads a letter from the input tape.
INPUT:
Nothing.
OUTPUT:
A letter.
Exception StopIteration is thrown if tape has reached the end.
EXAMPLES:
sage: from sage.combinat.finite_state_machine import FSMProcessIterator
sage: inverter = Transducer({'A': [('A', 0, 1), ('A', 1, 0)]},
....: initial_states=['A'], final_states=['A'])
sage: it = FSMProcessIterator(inverter, input_tape=[0, 1])
sage: it.read_letter()
0
Writes a letter on the output tape.
INPUT:
OUTPUT:
Nothing.
EXAMPLES:
sage: from sage.combinat.finite_state_machine import FSMProcessIterator
sage: inverter = Transducer({'A': [('A', 0, 1), ('A', 1, 0)]},
....: initial_states=['A'], final_states=['A'])
sage: it = FSMProcessIterator(inverter, input_tape=[0, 1])
sage: it.write_letter(42)
sage: it.output_tape
[42]
Writes a word on the output tape.
INPUT:
OUTPUT:
Nothing.
EXAMPLES:
sage: from sage.combinat.finite_state_machine import FSMProcessIterator
sage: inverter = Transducer({'A': [('A', 0, 1), ('A', 1, 0)]},
....: initial_states=['A'], final_states=['A'])
sage: it = FSMProcessIterator(inverter, input_tape=[0, 1])
sage: it.write_word([4, 2])
sage: it.output_tape
[4, 2]
Bases: sage.structure.sage_object.SageObject
Class for a state of a finite state machine.
INPUT:
OUTPUT:
Returns a state of a finite state machine.
EXAMPLES:
sage: from sage.combinat.finite_state_machine import FSMState
sage: A = FSMState('state 1', word_out=0, is_initial=True)
sage: A
'state 1'
sage: A.label()
'state 1'
sage: B = FSMState('state 2')
sage: A == B
False
Returns a (shallow) copy of the state.
INPUT:
Nothing.
OUTPUT:
A new state.
EXAMPLES:
sage: from sage.combinat.finite_state_machine import FSMState
sage: A = FSMState('A')
sage: copy(A)
'A'
Returns a deep copy of the state.
INPUT:
OUTPUT:
A new state.
EXAMPLES:
sage: from sage.combinat.finite_state_machine import FSMState
sage: A = FSMState('A')
sage: deepcopy(A)
'A'
Returns the label of the state.
INPUT:
Nothing.
OUTPUT:
The label of the state.
EXAMPLES:
sage: from sage.combinat.finite_state_machine import FSMState
sage: A = FSMState('state')
sage: A.label()
'state'
Returns a deep copy of the state with a new label.
INPUT:
OUTPUT:
A new state.
EXAMPLES:
sage: from sage.combinat.finite_state_machine import FSMState
sage: A = FSMState('A')
sage: A.relabeled('B')
'B'
Bases: sage.structure.sage_object.SageObject
Class for a transition of a finite state machine.
INPUT:
OUTPUT:
A transition of a finite state machine.
EXAMPLES:
sage: from sage.combinat.finite_state_machine import FSMState, FSMTransition
sage: A = FSMState('A')
sage: B = FSMState('B')
sage: S = FSMTransition(A, B, 0, 1)
sage: T = FSMTransition('A', 'B', 0, 1)
sage: T == S
True
sage: U = FSMTransition('A', 'B', 0)
sage: U == T
False
Returns a (shallow) copy of the transition.
INPUT:
Nothing.
OUTPUT:
A new transition.
EXAMPLES:
sage: from sage.combinat.finite_state_machine import FSMTransition
sage: t = FSMTransition('A', 'B', 0)
sage: copy(t)
Transition from 'A' to 'B': 0|-
Returns a deep copy of the transition.
INPUT:
OUTPUT:
A new transition.
EXAMPLES:
sage: from sage.combinat.finite_state_machine import FSMTransition
sage: t = FSMTransition('A', 'B', 0)
sage: deepcopy(t)
Transition from 'A' to 'B': 0|-
Returns a string of word. It may returns the symbol of the empty word FSMEmptyWordSymbol.
INPUT:
OUTPUT:
A string of word.
EXAMPLES:
sage: from sage.combinat.finite_state_machine import FSMWordSymbol
sage: FSMWordSymbol([0, 1, 1])
'0,1,1'
Bases: sage.structure.sage_object.SageObject
Class for a finite state machine.
A finite state machine is a finite set of states connected by transitions.
INPUT:
OUTPUT:
A finite state machine.
The object creation of Automaton and Transducer is the same as the one described here (i.e. just replace the word FiniteStateMachine by Automaton or Transducer).
Each transition of an automaton has an input label. Automata can, for example, be determinised (see Automaton.determinisation()) and minimized (see Automaton.minimization()). Each transition of a transducer has an input and an output label. Transducers can, for example, be simplified (see Transducer.simplification()).
EXAMPLES:
sage: from sage.combinat.finite_state_machine import FSMState, FSMTransition
See documentation for more examples.
We illustrate the different input formats:
The input-data can be a dictionary of dictionaries, where
The easiest is to use a tuple consisting of an input and an output word:
sage: FiniteStateMachine({'a':{'b':(0, 1), 'c':(1, 1)}})
Finite state machine with 3 states
Instead of the tuple anything iterable (e.g. a list) can be used as well.
If you want to use the arguments of FSMTransition directly, you can use a dictionary:
sage: FiniteStateMachine({'a':{'b':{'word_in':0, 'word_out':1},
....: 'c':{'word_in':1, 'word_out':1}}})
Finite state machine with 3 states
In the case you already have instances of FSMTransition, it is possible to use them directly:
sage: FiniteStateMachine({'a':{'b':FSMTransition('a', 'b', 0, 1),
....: 'c':FSMTransition('a', 'c', 1, 1)}})
Finite state machine with 3 states
The input-data can be a dictionary of lists, where the keys are states or label of states.
The list-elements can be states:
sage: a = FSMState('a')
sage: b = FSMState('b')
sage: c = FSMState('c')
sage: FiniteStateMachine({a:[b, c]})
Finite state machine with 3 states
Or the list-elements can simply be labels of states:
sage: FiniteStateMachine({'a':['b', 'c']})
Finite state machine with 3 states
The list-elements can also be transitions:
sage: FiniteStateMachine({'a':[FSMTransition('a', 'b', 0, 1),
....: FSMTransition('a', 'c', 1, 1)]})
Finite state machine with 3 states
Or they can be tuples of a label, an input word and an output word specifying a transition:
sage: FiniteStateMachine({'a':[('b', 0, 1), ('c', 1, 1)]})
Finite state machine with 3 states
The input-data can be a list, where its elements specify transitions:
sage: FiniteStateMachine([FSMTransition('a', 'b', 0, 1),
....: FSMTransition('a', 'c', 1, 1)])
Finite state machine with 3 states
It is possible to skip FSMTransition in the example above:
sage: FiniteStateMachine([('a', 'b', 0, 1), ('a', 'c', 1, 1)])
Finite state machine with 3 states
The parameters of the transition are given in tuples. Anyhow, anything iterable (e.g. a list) is possible.
You can also name the parameters of the transition. For this purpose you take a dictionary:
sage: FiniteStateMachine([{'from_state':'a', 'to_state':'b',
....: 'word_in':0, 'word_out':1},
....: {'from_state':'a', 'to_state':'c',
....: 'word_in':1, 'word_out':1}])
Finite state machine with 3 states
Other arguments, which FSMTransition accepts, can be added, too.
The input-data can also be function acting as transition function:
This function has two input arguments:
It returns a tuple with the following entries:
It may also output a list of such tuples if several transitions from the from-state and the input letter exist (this means that the finite state machine is non-deterministic).
If the transition does not exist, the function should raise a LookupError or return an empty list.
When constructing a finite state machine in this way, some inital states and an input alphabet have to be specified.
sage: def f(state_from, read):
....: if int(state_from) + read <= 2:
....: state_to = 2*int(state_from)+read
....: write = 0
....: else:
....: state_to = 2*int(state_from) + read - 5
....: write = 1
....: return (str(state_to), write)
sage: F = FiniteStateMachine(f, input_alphabet=[0, 1],
....: initial_states=['0'],
....: final_states=['0'])
sage: F([1, 0, 1])
(True, '0', [0, 0, 1])
The input-data can be an other instance of a finite state machine:
sage: FiniteStateMachine(FiniteStateMachine([]))
Traceback (most recent call last):
...
NotImplementedError
TESTS:
sage: a = FSMState('S_a', 'a')
sage: b = FSMState('S_b', 'b')
sage: c = FSMState('S_c', 'c')
sage: d = FSMState('S_d', 'd')
sage: FiniteStateMachine({a:[b, c], b:[b, c, d],
....: c:[a, b], d:[a, c]})
Finite state machine with 4 states
We have several constructions which lead to the same finite state machine:
sage: A = FSMState('A')
sage: B = FSMState('B')
sage: C = FSMState('C')
sage: FSM1 = FiniteStateMachine(
....: {A:{B:{'word_in':0, 'word_out':1},
....: C:{'word_in':1, 'word_out':1}}})
sage: FSM2 = FiniteStateMachine({A:{B:(0, 1), C:(1, 1)}})
sage: FSM3 = FiniteStateMachine(
....: {A:{B:FSMTransition(A, B, 0, 1),
....: C:FSMTransition(A, C, 1, 1)}})
sage: FSM4 = FiniteStateMachine({A:[(B, 0, 1), (C, 1, 1)]})
sage: FSM5 = FiniteStateMachine(
....: {A:[FSMTransition(A, B, 0, 1), FSMTransition(A, C, 1, 1)]})
sage: FSM6 = FiniteStateMachine(
....: [{'from_state':A, 'to_state':B, 'word_in':0, 'word_out':1},
....: {'from_state':A, 'to_state':C, 'word_in':1, 'word_out':1}])
sage: FSM7 = FiniteStateMachine([(A, B, 0, 1), (A, C, 1, 1)])
sage: FSM8 = FiniteStateMachine(
....: [FSMTransition(A, B, 0, 1), FSMTransition(A, C, 1, 1)])
sage: FSM1 == FSM2 == FSM3 == FSM4 == FSM5 == FSM6 == FSM7 == FSM8
True
It is possible to skip FSMTransition in the example above.
Some more tests for different input-data:
sage: FiniteStateMachine({'a':{'a':[0, 0], 'b':[1, 1]},
....: 'b':{'b':[1, 0]}})
Finite state machine with 2 states
sage: a = FSMState('S_a', 'a')
sage: b = FSMState('S_b', 'b')
sage: c = FSMState('S_c', 'c')
sage: d = FSMState('S_d', 'd')
sage: t1 = FSMTransition(a, b)
sage: t2 = FSMTransition(b, c)
sage: t3 = FSMTransition(b, d)
sage: t4 = FSMTransition(c, d)
sage: FiniteStateMachine([t1, t2, t3, t4])
Finite state machine with 4 states
TESTS:
sage: FiniteStateMachine().Kleene_closure()
Traceback (most recent call last):
...
NotImplementedError
Returns a new finite state machine with the accessible states of self and all transitions between those states.
INPUT:
Nothing.
OUTPUT:
A finite state machine with the accessible states of self and all transitions between those states.
A state is accessible if there is a directed path from an initial state to the state. If self has no initial states then a copy of the finite state machine self is returned.
EXAMPLES:
sage: F = Automaton([(0, 0, 0), (0, 1, 1), (1, 1, 0), (1, 0, 1)],
....: initial_states=[0])
sage: F.accessible_components()
Automaton with 2 states
sage: F = Automaton([(0, 0, 1), (0, 0, 1), (1, 1, 0), (1, 0, 1)],
....: initial_states=[0])
sage: F.accessible_components()
Automaton with 1 states
Constructs a finite state machine from a transition function.
INPUT:
OUTPUT:
Nothing.
EXAMPLES:
sage: F = FiniteStateMachine(initial_states=['A'],
....: input_alphabet=[0, 1])
sage: def f(state, input):
....: return [('A', input), ('B', 1-input)]
sage: F.add_from_transition_function(f)
sage: F.transitions()
[Transition from 'A' to 'A': 0|0,
Transition from 'A' to 'B': 0|1,
Transition from 'A' to 'A': 1|1,
Transition from 'A' to 'B': 1|0,
Transition from 'B' to 'A': 0|0,
Transition from 'B' to 'B': 0|1,
Transition from 'B' to 'A': 1|1,
Transition from 'B' to 'B': 1|0]
Initial states can also be given as a parameter:
sage: F = FiniteStateMachine(input_alphabet=[0,1])
sage: def f(state, input):
....: return [('A', input), ('B', 1-input)]
sage: F.add_from_transition_function(f,initial_states=['A'])
sage: F.initial_states()
['A']
Already existing states in the finite state machine (the final states in the example below) are also explored:
sage: F = FiniteStateMachine(initial_states=[0],
....: final_states=[1],
....: input_alphabet=[0])
sage: def transition_function(state, letter):
....: return(1-state, [])
sage: F.add_from_transition_function(transition_function)
sage: F.transitions()
[Transition from 0 to 1: 0|-,
Transition from 1 to 0: 0|-]
If explore_existing_states=False, however, this behavior is turned off, i.e., already existing states are not explored:
sage: F = FiniteStateMachine(initial_states=[0],
....: final_states=[1],
....: input_alphabet=[0])
sage: def transition_function(state, letter):
....: return(1-state, [])
sage: F.add_from_transition_function(transition_function,
....: explore_existing_states=False)
sage: F.transitions()
[Transition from 0 to 1: 0|-]
TEST:
sage: F = FiniteStateMachine(initial_states=['A'])
sage: def f(state, input):
....: return [('A', input), ('B', 1-input)]
sage: F.add_from_transition_function(f)
Traceback (most recent call last):
...
ValueError: No input alphabet is given.
Try calling determine_alphabets().
Adds a state to the finite state machine and returns the new state. If the state already exists, that existing state is returned.
INPUT:
OUTPUT:
The new or existing state.
EXAMPLES:
sage: from sage.combinat.finite_state_machine import FSMState
sage: F = FiniteStateMachine()
sage: A = FSMState('A', is_initial=True)
sage: F.add_state(A)
'A'
Adds several states. See add_state for more information.
INPUT:
OUTPUT:
Nothing.
EXAMPLES:
sage: F = FiniteStateMachine()
sage: F.add_states(['A', 'B'])
sage: F.states()
['A', 'B']
Adds a transition to the finite state machine and returns the new transition. If the transition already exists, that existing transition is returned.
INPUT:
The following forms are all accepted:
sage: from sage.combinat.finite_state_machine import FSMState, FSMTransition
sage: A = FSMState('A')
sage: B = FSMState('B')
sage: FSM = FiniteStateMachine()
sage: FSM.add_transition(FSMTransition(A, B, 0, 1))
Transition from 'A' to 'B': 0|1
sage: FSM = FiniteStateMachine()
sage: FSM.add_transition(A, B, 0, 1)
Transition from 'A' to 'B': 0|1
sage: FSM = FiniteStateMachine()
sage: FSM.add_transition(A, B, word_in=0, word_out=1)
Transition from 'A' to 'B': 0|1
sage: FSM = FiniteStateMachine()
sage: FSM.add_transition('A', 'B', {'word_in': 0, 'word_out': 1})
Transition from 'A' to 'B': {'word_in': 0, 'word_out': 1}|-
sage: FSM = FiniteStateMachine()
sage: FSM.add_transition(from_state=A, to_state=B,
....: word_in=0, word_out=1)
Transition from 'A' to 'B': 0|1
sage: FSM = FiniteStateMachine()
sage: FSM.add_transition({'from_state': A, 'to_state': B,
....: 'word_in': 0, 'word_out': 1})
Transition from 'A' to 'B': 0|1
sage: FSM = FiniteStateMachine()
sage: FSM.add_transition((A, B, 0, 1))
Transition from 'A' to 'B': 0|1
sage: FSM = FiniteStateMachine()
sage: FSM.add_transition([A, B, 0, 1])
Transition from 'A' to 'B': 0|1
If the states A and B are not instances of FSMState, then it is assumed that they are labels of states.
OUTPUT:
The new or existing transition.
Adds a transition if function(state, state) says that there is one.
INPUT:
OUTPUT:
Nothing.
EXAMPLES:
sage: F = FiniteStateMachine()
sage: F.add_states(['A', 'B', 'C'])
sage: def f(state1, state2):
....: if state1 == 'C':
....: return None
....: return (0, 1)
sage: F.add_transitions_from_function(f)
sage: len(F.transitions())
6
Returns the adjacency matrix of the underlying graph.
INPUT:
OUTPUT:
A matrix.
If any label of a state is not an integer, the finite state machine is relabeled at the beginning. If there are more than one transitions between two states, then the different return values of entry are added up.
The default value of entry takes the variable x to the power of the output word of the transition.
EXAMPLES:
sage: B = FiniteStateMachine({0:{0:(0, 0), 'a':(1, 0)},
....: 'a':{2:(0, 0), 3:(1, 0)},
....: 2:{0:(1, 1), 4:(0, 0)},
....: 3:{'a':(0, 1), 2:(1, 1)},
....: 4:{4:(1, 1), 3:(0, 1)}},
....: initial_states=[0])
sage: B.adjacency_matrix()
[1 1 0 0 0]
[0 0 1 1 0]
[x 0 0 0 1]
[0 x x 0 0]
[0 0 0 x x]
sage: B.adjacency_matrix(entry=(lambda transition: 1))
[1 1 0 0 0]
[0 0 1 1 0]
[1 0 0 0 1]
[0 1 1 0 0]
[0 0 0 1 1]
sage: B.adjacency_matrix(1, entry=(lambda transition:
....: exp(I*transition.word_out[0]*var('t'))))
[ 0 1 0 0 0]
[ 0 0 0 1 0]
[e^(I*t) 0 0 0 0]
[ 0 0 e^(I*t) 0 0]
[ 0 0 0 0 e^(I*t)]
Returns a new finite state machine, which is the cartesian product of self and other.
INPUT:
OUTPUT:
A new finite state machine, which is the cartesian product of self and other.
The set of states of the new automaton is the cartesian product of the set of states of both given automata. There is a transition \(((A, B), (C, D), a)\) in the new automaton if there are transitions \((A, C, a)\) and \((B, C, a)\) in the old automata.
EXAMPLES:
sage: aut1 = Automaton([('1', '2', 1), ('2', '2', 1), ('2', '2', 0)],
....: initial_states=['1'], final_states=['2'],
....: determine_alphabets=True)
sage: aut2 = Automaton([('A', 'A', 1), ('A', 'B', 1),
....: ('B', 'B', 0), ('B', 'A', 0)],
....: initial_states=['A'], final_states=['B'],
....: determine_alphabets=True)
sage: res = aut1.cartesian_product(aut2)
sage: res.transitions()
[Transition from ('1', 'A') to ('2', 'A'): 1|-,
Transition from ('1', 'A') to ('2', 'B'): 1|-,
Transition from ('2', 'A') to ('2', 'A'): 1|-,
Transition from ('2', 'A') to ('2', 'B'): 1|-,
Transition from ('2', 'B') to ('2', 'B'): 0|-,
Transition from ('2', 'B') to ('2', 'A'): 0|-]
Returns a new transducer which is the composition of self and other.
INPUT:
other – a transducer
algorithm – can be one of the following
direct – The composition is calculated directly.
There can be arbitrarily many initial and final states, but the input and output labels must have length 1.
WARNING: The output of other is fed into self.
explorative – An explorative algorithm is used.
At least the following restrictions apply, but are not checked: - both self and other have exactly one initial state - all input labels of transitions have length exactly 1
The input alphabet of self has to be specified.
This is a very limited implementation of composition. WARNING: The output of other is fed into self.
If algorithm is None, then the algorithm is chosen automatically (at the moment always direct).
OUTPUT:
A new transducer.
The labels of the new finite state machine are pairs of states of the original finite state machines.
EXAMPLES:
sage: F = Transducer([('A', 'B', 1, 0), ('B', 'A', 0, 1)],
....: initial_states=['A', 'B'], final_states=['B'],
....: determine_alphabets=True)
sage: G = Transducer([(1, 1, 1, 0), (1, 2, 0, 1),
....: (2, 2, 1, 1), (2, 2, 0, 0)],
....: initial_states=[1], final_states=[2],
....: determine_alphabets=True)
sage: Hd = F.composition(G, algorithm='direct')
sage: Hd.initial_states()
[(1, 'B'), (1, 'A')]
sage: Hd.transitions()
[Transition from (1, 'B') to (1, 'A'): 1|1,
Transition from (1, 'A') to (2, 'B'): 0|0,
Transition from (2, 'B') to (2, 'A'): 0|1,
Transition from (2, 'A') to (2, 'B'): 1|0]
sage: F = Transducer([('A', 'B', 1, [1, 0]), ('B', 'B', 1, 1),
....: ('B', 'B', 0, 0)],
....: initial_states=['A'], final_states=['B'])
sage: G = Transducer([(1, 1, 0, 0), (1, 2, 1, 0),
....: (2, 2, 0, 1), (2, 1, 1, 1)],
....: initial_states=[1], final_states=[1])
sage: He = G.composition(F, algorithm='explorative')
sage: He.transitions()
[Transition from ('A', 1) to ('B', 2): 1|0,1,
Transition from ('B', 2) to ('B', 2): 0|1,
Transition from ('B', 2) to ('B', 1): 1|1,
Transition from ('B', 1) to ('B', 1): 0|0,
Transition from ('B', 1) to ('B', 2): 1|0]
Be aware that after composition, different transitions may share the same output label (same python object):
sage: F = Transducer([ ('A','B',0,0), ('B','A',0,0)],
....: initial_states=['A'],
....: final_states=['A'])
sage: F.transitions()[0].word_out is F.transitions()[1].word_out
False
sage: G = Transducer([('C','C',0,1)],)
....: initial_states=['C'],
....: final_states=['C'])
sage: H = G.composition(F)
sage: H.transitions()[0].word_out is H.transitions()[1].word_out
True
TESTS:
Due to the limitations of the two algorithms the following (examples from above, but different algorithm used) does not give a full answer or does not work
In the following, algorithm='explorative' is inadequate, as F has more than one initial state:
sage: F = Transducer([('A', 'B', 1, 0), ('B', 'A', 0, 1)],
....: initial_states=['A', 'B'], final_states=['B'],
....: determine_alphabets=True)
sage: G = Transducer([(1, 1, 1, 0), (1, 2, 0, 1),
....: (2, 2, 1, 1), (2, 2, 0, 0)],
....: initial_states=[1], final_states=[2],
....: determine_alphabets=True)
sage: He = F.composition(G, algorithm='explorative')
sage: He.initial_states()
[(1, 'A')]
sage: He.transitions()
[Transition from (1, 'A') to (2, 'B'): 0|0,
Transition from (2, 'B') to (2, 'A'): 0|1,
Transition from (2, 'A') to (2, 'B'): 1|0]
In the following example, algorithm='direct' is inappropriate as there are edges with output labels of length greater than 1:
sage: F = Transducer([('A', 'B', 1, [1, 0]), ('B', 'B', 1, 1),
....: ('B', 'B', 0, 0)],
....: initial_states=['A'], final_states=['B'])
sage: G = Transducer([(1, 1, 0, 0), (1, 2, 1, 0),
....: (2, 2, 0, 1), (2, 1, 1, 1)],
....: initial_states=[1], final_states=[1])
sage: Hd = G.composition(F, algorithm='direct')
TESTS:
sage: F = FiniteStateMachine([('A', 'A')])
sage: FiniteStateMachine().concatenation(F)
Traceback (most recent call last):
...
NotImplementedError
Returns a (shallow) copy of the finite state machine.
INPUT:
Nothing.
OUTPUT:
A new finite state machine.
TESTS:
sage: copy(FiniteStateMachine())
Traceback (most recent call last):
...
NotImplementedError
Returns a deep copy of the finite state machine.
INPUT:
OUTPUT:
A new finite state machine.
EXAMPLES:
sage: F = FiniteStateMachine([('A', 'A', 0, 1), ('A', 'A', 1, 0)])
sage: deepcopy(F)
Finite state machine with 1 states
Deletes a state and all transitions coming or going to this state.
INPUT:
OUTPUT:
Nothing.
EXAMPLES:
sage: from sage.combinat.finite_state_machine import FSMTransition
sage: t1 = FSMTransition('A', 'B', 0)
sage: t2 = FSMTransition('B', 'B', 1)
sage: F = FiniteStateMachine([t1, t2])
sage: F.delete_state('A')
sage: F. transitions()
[Transition from 'B' to 'B': 1|-]
Deletes a transition by removing it from the list of transitions of the state, where the transition starts.
INPUT:
OUTPUT:
Nothing.
EXAMPLES:
sage: F = FiniteStateMachine([('A', 'B', 0), ('B', 'A', 1)])
sage: F.delete_transition(('A', 'B', 0))
sage: F.transitions()
[Transition from 'B' to 'A': 1|-]
Determines the input and output alphabet according to the transitions in self.
INPUT:
OUTPUT:
Nothing.
After this operation the input alphabet and the output alphabet of self are a list of letters.
EXAMPLES:
sage: T = Transducer([(1, 1, 1, 0), (1, 2, 2, 1),
....: (2, 2, 1, 1), (2, 2, 0, 0)],
....: determine_alphabets=False)
sage: (T.input_alphabet, T.output_alphabet)
(None, None)
sage: T.determine_alphabets()
sage: (T.input_alphabet, T.output_alphabet)
([0, 1, 2], [0, 1])
Returns the graph of the finite state machine with labeled vertices and labeled edges.
INPUT:
OUTPUT:
A graph.
EXAMPLES:
sage: from sage.combinat.finite_state_machine import FSMState
sage: A = FSMState('A')
sage: T = Transducer()
sage: T.graph()
Digraph on 0 vertices
sage: T.add_state(A)
'A'
sage: T.graph()
Digraph on 1 vertex
sage: T.add_transition(('A', 'A', 0, 1))
Transition from 'A' to 'A': 0|1
sage: T.graph()
Looped digraph on 1 vertex
TESTS:
sage: F = FiniteStateMachine([('A', 'A')])
sage: FiniteStateMachine().disjoint_union(F)
Traceback (most recent call last):
...
NotImplementedError
Returns an empty deep copy of the finite state machine, i.e., input_alphabet, output_alphabet are preserved, but states and transitions are not.
INPUT:
OUTPUT:
A new finite state machine.
EXAMPLES:
sage: F = FiniteStateMachine([('A', 'A', 0, 2), ('A', 'A', 1, 3)],
....: input_alphabet=[0,1],
....: output_alphabet=[2,3])
sage: FE = F.empty_copy(); FE
Finite state machine with 0 states
sage: FE.input_alphabet
[0, 1]
sage: FE.output_alphabet
[2, 3]
Returns a list of equivalence classes of states.
INPUT:
Nothing.
OUTPUT:
A list of equivalence classes of states.
Two states \(a\) and \(b\) are equivalent, if and only if for each input label word_in the following holds:
For paths \(p_a\) from \(a\) to \(a'\) with input label word_in and output label word_out_a and \(p_b\) from \(b\) to \(b'\) with input label word_in and output label word_out_b, we have word_out_a=word_out_b, \(a'\) and \(b'\) have the same output label and are both final or both non-final.
The function equivalence_classes() returns a list of the equivalence classes to this equivalence relation.
This is one step of Moore’s minimization algorithm.
See also
EXAMPLES:
sage: fsm = FiniteStateMachine([("A", "B", 0, 1), ("A", "B", 1, 0),
....: ("B", "C", 0, 0), ("B", "C", 1, 1),
....: ("C", "D", 0, 1), ("C", "D", 1, 0),
....: ("D", "A", 0, 0), ("D", "A", 1, 1)])
sage: fsm.equivalence_classes()
[['A', 'C'], ['B', 'D']]
Returns a list of all final states.
INPUT:
Nothing.
OUTPUT:
A list of all final states.
EXAMPLES:
sage: from sage.combinat.finite_state_machine import FSMState
sage: A = FSMState('A', is_final=True)
sage: B = FSMState('B', is_initial=True)
sage: C = FSMState('C', is_final=True)
sage: F = FiniteStateMachine([(A, B), (A, C)])
sage: F.final_states()
['A', 'C']
Returns the graph of the finite state machine with labeled vertices and labeled edges.
INPUT:
OUTPUT:
A graph.
EXAMPLES:
sage: from sage.combinat.finite_state_machine import FSMState
sage: A = FSMState('A')
sage: T = Transducer()
sage: T.graph()
Digraph on 0 vertices
sage: T.add_state(A)
'A'
sage: T.graph()
Digraph on 1 vertex
sage: T.add_transition(('A', 'A', 0, 1))
Transition from 'A' to 'A': 0|1
sage: T.graph()
Looped digraph on 1 vertex
Returns whether state is one of the final states of the finite state machine.
INPUT:
OUTPUT:
True or False.
EXAMPLES:
sage: FiniteStateMachine(final_states=['A']).has_final_state('A')
True
Returns whether the finite state machine has a final state.
INPUT:
Nothing.
OUTPUT:
True or False.
EXAMPLES:
sage: FiniteStateMachine().has_final_states()
False
Returns whether state is one of the initial states of the finite state machine.
INPUT:
OUTPUT:
True or False.
EXAMPLES:
sage: F = FiniteStateMachine([('A', 'A')], initial_states=['A'])
sage: F.has_initial_state('A')
True
Returns whether the finite state machine has an initial state.
INPUT:
Nothing.
OUTPUT:
True or False.
EXAMPLES:
sage: FiniteStateMachine().has_initial_states()
False
Returns whether state is one of the states of the finite state machine.
INPUT:
OUTPUT:
True or False.
EXAMPLES:
sage: FiniteStateMachine().has_state('A')
False
Returns whether transition is one of the transitions of the finite state machine.
INPUT:
OUTPUT:
True or False.
EXAMPLES:
sage: from sage.combinat.finite_state_machine import FSMTransition
sage: t = FSMTransition('A', 'A', 0, 1)
sage: FiniteStateMachine().has_transition(t)
False
sage: FiniteStateMachine().has_transition(('A', 'A', 0, 1))
Traceback (most recent call last):
...
TypeError: Transition is not an instance of FSMTransition.
Returns a list of all initial states.
INPUT:
Nothing.
OUTPUT:
A list of all initial states.
EXAMPLES:
sage: from sage.combinat.finite_state_machine import FSMState
sage: A = FSMState('A', is_initial=True)
sage: B = FSMState('B')
sage: F = FiniteStateMachine([(A, B, 1, 0)])
sage: F.initial_states()
['A']
Returns an automaton where the output of each transition of self is deleted.
INPUT:
Nothing
OUTPUT:
An automaton.
EXAMPLES:
sage: F = FiniteStateMachine([('A', 'B', 0, 1), ('A', 'A', 1, 1),
....: ('B', 'B', 1, 0)])
sage: G = F.input_projection()
sage: G.transitions()
[Transition from 'A' to 'B': 0|-,
Transition from 'A' to 'A': 1|-,
Transition from 'B' to 'B': 1|-]
TESTS:
sage: F = FiniteStateMachine([('A', 'A')])
sage: FiniteStateMachine().intersection(F)
Traceback (most recent call last):
...
NotImplementedError
TESTS:
sage: FiniteStateMachine().is_connected()
Traceback (most recent call last):
...
NotImplementedError
Returns whether the finite finite state machine is deterministic.
INPUT:
Nothing.
OUTPUT:
True or False.
A finite state machine is considered to be deterministic if each transition has input label of length one and for each pair \((q,a)\) where \(q\) is a state and \(a\) is an element of the input alphabet, there is at most one transition from \(q\) with input label \(a\).
TESTS:
sage: fsm = FiniteStateMachine()
sage: fsm.add_transition(('A', 'B', 0, []))
Transition from 'A' to 'B': 0|-
sage: fsm.is_deterministic()
True
sage: fsm.add_transition(('A', 'C', 0, []))
Transition from 'A' to 'C': 0|-
sage: fsm.is_deterministic()
False
sage: fsm.add_transition(('A', 'B', [0,1], []))
Transition from 'A' to 'B': 0,1|-
sage: fsm.is_deterministic()
False
Returns an iterator of the final states.
INPUT:
Nothing.
OUTPUT:
An iterator over all initial states.
EXAMPLES:
sage: from sage.combinat.finite_state_machine import FSMState
sage: A = FSMState('A', is_final=True)
sage: B = FSMState('B', is_initial=True)
sage: C = FSMState('C', is_final=True)
sage: F = FiniteStateMachine([(A, B), (A, C)])
sage: [s.label() for s in F.iter_final_states()]
['A', 'C']
Returns an iterator of the initial states.
INPUT:
Nothing.
OUTPUT:
An iterator over all initial states.
EXAMPLES:
sage: from sage.combinat.finite_state_machine import FSMState
sage: A = FSMState('A', is_initial=True)
sage: B = FSMState('B')
sage: F = FiniteStateMachine([(A, B, 1, 0)])
sage: [s.label() for s in F.iter_initial_states()]
['A']
See \(process\) for more informations.
EXAMPLES:
sage: inverter = Transducer({'A': [('A', 0, 1), ('A', 1, 0)]},
....: initial_states=['A'], final_states=['A'])
sage: it = inverter.iter_process(input_tape=[0, 1, 1])
sage: for _ in it:
....: pass
sage: it.output_tape
[1, 0, 0]
Returns an iterator of the states.
INPUT:
Nothing.
OUTPUT:
An iterator of the states of the finite state machine.
EXAMPLES:
sage: FSM = Automaton([('1', '2', 1), ('2', '2', 0)])
sage: [s.label() for s in FSM.iter_states()]
['1', '2']
Returns an iterator of all transitions.
INPUT:
OUTPUT:
An iterator of all transitions.
EXAMPLES:
sage: FSM = Automaton([('1', '2', 1), ('2', '2', 0)])
sage: [(t.from_state.label(), t.to_state.label())
....: for t in FSM.iter_transitions('1')]
[('1', '2')]
sage: [(t.from_state.label(), t.to_state.label())
....: for t in FSM.iter_transitions('2')]
[('2', '2')]
sage: [(t.from_state.label(), t.to_state.label())
....: for t in FSM.iter_transitions()]
[('1', '2'), ('2', '2')]
Returns a automaton where the input of each transition of self is deleted and the new input is the original output.
INPUT:
Nothing
OUTPUT:
An automaton.
EXAMPLES:
sage: F = FiniteStateMachine([('A', 'B', 0, 1), ('A', 'A', 1, 1),
....: ('B', 'B', 1, 0)])
sage: G = F.output_projection()
sage: G.transitions()
[Transition from 'A' to 'B': 1|-,
Transition from 'A' to 'A': 1|-,
Transition from 'B' to 'B': 0|-]
Plots a graph of the finite state machine with labeled vertices and labeled edges.
INPUT:
Nothing.
OUTPUT:
A plot of the graph of the finite state machine.
TESTS:
sage: FiniteStateMachine([('A', 'A', 0)]).plot()
Lists all predecessors of a state.
INPUT:
OUTPUT:
A list of states.
EXAMPLES:
sage: A = Transducer([('I', 'A', 'a', 'b'), ('I', 'B', 'b', 'c'),
....: ('I', 'C', 'c', 'a'), ('A', 'F', 'b', 'a'),
....: ('B', 'F', ['c', 'b'], 'b'), ('C', 'F', 'a', 'c')],
....: initial_states=['I'], final_states=['F'])
sage: A.predecessors(A.state('A'))
['A', 'I']
sage: A.predecessors(A.state('F'), valid_input=['b', 'a'])
['F', 'C', 'A', 'I']
sage: A.predecessors(A.state('F'), valid_input=[['c', 'b'], 'a'])
['F', 'C', 'B']
Apply the following to each state \(s\) (except initial and final states) of the finite state machine as often as possible:
If the letter a is prefix of the output label of all transitions from \(s\), then remove it from all these labels and append it to all output labels of all transitions leading to \(s\).
We assume that the states have no output labels.
INPUT:
Nothing.
OUTPUT:
Nothing.
EXAMPLES:
sage: A = Transducer([('A', 'B', 1, 1), ('B', 'B', 0, 0), ('B', 'C', 1, 0)],
....: initial_states=['A'], final_states=['C'])
sage: A.prepone_output()
sage: A.transitions()
[Transition from 'A' to 'B': 1|1,0,
Transition from 'B' to 'B': 0|0,
Transition from 'B' to 'C': 1|-]
sage: B = Transducer([('A', 'B', 0, 1), ('B', 'C', 1, [1, 1]), ('B', 'C', 0, 1)],
....: initial_states=['A'], final_states=['C'])
sage: B.prepone_output()
sage: B.transitions()
[Transition from 'A' to 'B': 0|1,1,
Transition from 'B' to 'C': 1|1,
Transition from 'B' to 'C': 0|-]
If initial states are not labeled as such, unexpected results may be obtained:
sage: C = Transducer([(0,1,0,0)])
sage: C.prepone_output()
prepone_output: All transitions leaving state 0 have an
output label with prefix 0. However, there is no inbound
transition and it is not an initial state. This routine
(possibly called by simplification) therefore erased this
prefix from all outbound transitions.
sage: C.transitions()
[Transition from 0 to 1: 0|-]
Returns whether the finite state machine accepts the input, the state where the computation stops and which output is generated.
INPUT:
OUTPUT:
A triple, where
Note that in the case the finite state machine is not deterministic, one possible path is gone. This means, that in this case the output can be wrong. Use determinisation() to get a deterministic finite state machine and try again.
EXAMPLES:
sage: from sage.combinat.finite_state_machine import FSMState
sage: A = FSMState('A', is_initial = True, is_final = True)
sage: binary_inverter = Transducer({A:[(A, 0, 1), (A, 1, 0)]})
sage: binary_inverter.process([0, 1, 0, 0, 1, 1])
(True, 'A', [1, 0, 1, 1, 0, 0])
Alternatively, we can invoke this function by:
sage: binary_inverter([0, 1, 0, 0, 1, 1])
(True, 'A', [1, 0, 1, 1, 0, 0])
sage: NAF_ = FSMState('_', is_initial = True, is_final = True)
sage: NAF1 = FSMState('1', is_final = True)
sage: NAF = Automaton(
....: {NAF_: [(NAF_, 0), (NAF1, 1)], NAF1: [(NAF_, 0)]})
sage: [NAF.process(w)[0] for w in [[0], [0, 1], [1, 1], [0, 1, 0, 1],
....: [0, 1, 1, 1, 0], [1, 0, 0, 1, 1]]]
[True, True, False, True, False, False]
Returns a new finite state machine whose states are pairs of states of the original finite state machines.
INPUT:
OUTPUT:
A finite state machine whose states are pairs of states of the original finite state machines.
The labels of the transitions are defined by function.
EXAMPLES:
sage: F = Automaton([('A', 'B', 1), ('A', 'A', 0), ('B', 'A', 2)],
....: initial_states=['A'], final_states=['B'],
....: determine_alphabets=True)
sage: G = Automaton([(1, 1, 1)], initial_states=[1], final_states=[1])
sage: def addition(transition1, transition2):
....: return (transition1.word_in[0] + transition2.word_in[0],
....: None)
sage: H = F.product_FiniteStateMachine(G, addition, [0, 1, 2, 3], only_accessible_components=False)
sage: H.transitions()
[Transition from ('A', 1) to ('B', 1): 2|-,
Transition from ('A', 1) to ('A', 1): 1|-,
Transition from ('B', 1) to ('A', 1): 3|-]
sage: H1 = F.product_FiniteStateMachine(G, addition, [0, 1, 2, 3], only_accessible_components=False)
sage: H1.states()[0].label()[0] is F.states()[0]
True
sage: H1.states()[0].label()[1] is G.states()[0]
True
sage: F = Automaton([(0,1,1/4), (0,0,3/4), (1,1,3/4), (1,0,1/4)],
....: initial_states=[0] )
sage: G = Automaton([(0,0,1), (1,1,3/4), (1,0,1/4)],
....: initial_states=[0] )
sage: H = F.product_FiniteStateMachine(
....: G, lambda t1,t2: (t1.word_in[0]*t2.word_in[0], None))
sage: H.states()
[(0, 0), (1, 0)]
sage: F = Automaton([(0,1,1/4), (0,0,3/4), (1,1,3/4), (1,0,1/4)],
....: initial_states=[0] )
sage: G = Automaton([(0,0,1), (1,1,3/4), (1,0,1/4)],
....: initial_states=[0] )
sage: H = F.product_FiniteStateMachine(G,
....: lambda t1,t2: (t1.word_in[0]*t2.word_in[0], None),
....: only_accessible_components=False)
sage: H.states()
[(0, 0), (1, 0), (0, 1), (1, 1)]
Returns an Automaton which transition labels are the projection of the transition labels of the input.
INPUT:
OUTPUT:
An automaton.
EXAMPLES:
sage: F = FiniteStateMachine([('A', 'B', 0, 1), ('A', 'A', 1, 1),
....: ('B', 'B', 1, 0)])
sage: G = F.projection(what='output')
sage: G.transitions()
[Transition from 'A' to 'B': 1|-,
Transition from 'A' to 'A': 1|-,
Transition from 'B' to 'B': 0|-]
Constructs the quotient with respect to the equivalence classes.
INPUT:
OUTPUT:
A finite state machine.
Assume that \(c\) is a class and \(s\), \(s'\) are states in \(c\). If there is a transition from \(s\) to some \(t\) with input label word_in and output label word_out, then there has to be a transition from \(s'\) to some \(t'\) with input label word_in and output label word_out such that \(s'\) and \(t'\) are states of the same class \(c'\). Then there is a transition from \(c\) to \(c'\) in the quotient with input label word_in and output label word_out.
Non-initial states may be merged with initial states, the resulting state is an initial state.
All states in a class must have the same is_final and word_out values.
EXAMPLES:
sage: fsm = FiniteStateMachine([("A", "B", 0, 1), ("A", "B", 1, 0),
....: ("B", "C", 0, 0), ("B", "C", 1, 1),
....: ("C", "D", 0, 1), ("C", "D", 1, 0),
....: ("D", "A", 0, 0), ("D", "A", 1, 1)])
sage: fsmq = fsm.quotient([[fsm.state("A"), fsm.state("C")],
....: [fsm.state("B"), fsm.state("D")]])
sage: fsmq.transitions()
[Transition from ('A', 'C')
to ('B', 'D'): 0|1,
Transition from ('A', 'C')
to ('B', 'D'): 1|0,
Transition from ('B', 'D')
to ('A', 'C'): 0|0,
Transition from ('B', 'D')
to ('A', 'C'): 1|1]
sage: fsmq.relabeled().transitions()
[Transition from 0 to 1: 0|1,
Transition from 0 to 1: 1|0,
Transition from 1 to 0: 0|0,
Transition from 1 to 0: 1|1]
sage: fsmq1 = fsm.quotient(fsm.equivalence_classes())
sage: fsmq1 == fsmq
True
sage: fsm.quotient([[fsm.state("A"), fsm.state("B"), fsm.state("C"), fsm.state("D")]])
Traceback (most recent call last):
...
ValueError: There is a transition Transition from 'B' to 'C': 0|0 in the original transducer, but no corresponding transition in the new transducer.
Returns a deep copy of the finite state machine, but the states are relabeled by integers starting with 0.
INPUT:
OUTPUT:
A new finite state machine.
EXAMPLES:
sage: FSM1 = FiniteStateMachine([('A', 'B'), ('B', 'C'), ('C', 'A')])
sage: FSM1.states()
['A', 'B', 'C']
sage: FSM2 = FSM1.relabeled()
sage: FSM2.states()
[0, 1, 2]
TESTS:
sage: FiniteStateMachine().remove_epsilon_transitions()
Traceback (most recent call last):
...
NotImplementedError
Returns a new transducer, where all transitions in self with input labels consisting of more than one letter are replaced by a path of the corresponding length.
INPUT:
Nothing.
OUTPUT:
A new transducer.
EXAMPLES:
sage: A = Transducer([('A', 'B', [1, 2, 3], 0)],
....: initial_states=['A'], final_states=['B'])
sage: A.split_transitions().states()
[('A', ()), ('B', ()),
('A', (1,)), ('A', (1, 2))]
Returns the state of the finite state machine.
INPUT:
OUTPUT:
Returns the state of the finite state machine corresponding to state.
If no state is found, then a LookupError is thrown.
EXAMPLES:
sage: from sage.combinat.finite_state_machine import FSMState
sage: A = FSMState('A')
sage: FSM = FiniteStateMachine([(A, 'B'), ('C', A)])
sage: FSM.state('A') == A
True
sage: FSM.state('xyz')
Traceback (most recent call last):
...
LookupError: No state with label xyz found.
Returns the states of the finite state machine.
INPUT:
Nothing.
OUTPUT:
The states of the finite state machine as list.
EXAMPLES:
sage: FSM = Automaton([('1', '2', 1), ('2', '2', 0)])
sage: FSM.states()
['1', '2']
Returns the transition of the finite state machine.
INPUT:
OUTPUT:
Returns the transition of the finite state machine corresponding to transition.
If no transition is found, then a LookupError is thrown.
EXAMPLES:
sage: from sage.combinat.finite_state_machine import FSMTransition
sage: t = FSMTransition('A', 'B', 0)
sage: F = FiniteStateMachine([t])
sage: F.transition(('A', 'B', 0))
Transition from 'A' to 'B': 0|-
sage: id(t) == id(F.transition(('A', 'B', 0)))
True
Returns a list of all transitions.
INPUT:
OUTPUT:
A list of all transitions.
EXAMPLES:
sage: FSM = Automaton([('1', '2', 1), ('2', '2', 0)])
sage: FSM.transitions()
[Transition from '1' to '2': 1|-,
Transition from '2' to '2': 0|-]
Returns a new finite state machine, where all transitions of the input finite state machine are reversed.
INPUT:
Nothing.
OUTPUT:
A new finite state machine.
EXAMPLES:
sage: aut = Automaton([('A', 'A', 0), ('A', 'A', 1), ('A', 'B', 0)],
....: initial_states=['A'], final_states=['B'])
sage: aut.transposition().transitions('B')
[Transition from 'B' to 'A': 0|-]
sage: aut = Automaton([('1', '1', 1), ('1', '2', 0), ('2', '2', 0)],
....: initial_states=['1'], final_states=['1', '2'])
sage: aut.transposition().initial_states()
['1', '2']
Bases: sage.combinat.finite_state_machine.FiniteStateMachine
This creates a transducer, which is a finite state machine, whose transitions have input and output labels.
An transducer has additional features like creating a simplified transducer.
See class FiniteStateMachine for more information.
EXAMPLES:
We can create a transducer performing the addition of 1 (for numbers given in binary and read from right to left) in the following way:
sage: T = Transducer([('C', 'C', 1, 0), ('C', 'N', 0, 1),
....: ('N', 'N', 0, 0), ('N', 'N', 1, 1)],
....: initial_states=['C'], final_states=['N'])
sage: T
Transducer with 2 states
sage: T([0])
(True, 'N', [1])
sage: T([1,1,0])
(True, 'N', [0, 0, 1])
sage: ZZ(T(15.digits(base=2)+[0])[2], base=2)
16
Note that we have padded the binary input sequence by a \(0\) so that the transducer can reach its final state.
TESTS:
sage: Transducer()
Transducer with 0 states
Returns a simplified transducer.
INPUT:
Nothing.
OUTPUT:
A new transducer.
This function simplifies a transducer by Moore’s algorithm, first moving common output labels of transitions leaving a state to output labels of transitions entering the state (cf. prepone_output()).
The resulting transducer implements the same function as the original transducer.
EXAMPLES:
sage: fsm = Transducer([("A", "B", 0, 1), ("A", "B", 1, 0),
....: ("B", "C", 0, 0), ("B", "C", 1, 1),
....: ("C", "D", 0, 1), ("C", "D", 1, 0),
....: ("D", "A", 0, 0), ("D", "A", 1, 1)])
sage: fsms = fsm.simplification()
sage: fsms
Transducer with 2 states
sage: fsms.transitions()
[Transition from ('A', 'C')
to ('B', 'D'): 0|1,
Transition from ('A', 'C')
to ('B', 'D'): 1|0,
Transition from ('B', 'D')
to ('A', 'C'): 0|0,
Transition from ('B', 'D')
to ('A', 'C'): 1|1]
sage: fsms.relabeled().transitions()
[Transition from 0 to 1: 0|1,
Transition from 0 to 1: 1|0,
Transition from 1 to 0: 0|0,
Transition from 1 to 0: 1|1]
Group iterable l by values of key.
INPUT:
OUTPUT:
A list of pairs (k, elements) such that key(e)=k for all e in elements.
This is similar to itertools.groupby except that lists are returned instead of iterables and no prior sorting is required.
We do not require
However, it is required
The implementation is inspired by http://stackoverflow.com/a/15250161, but non-hashable keys are allowed.
EXAMPLES:
sage: from sage.combinat.finite_state_machine import full_group_by
sage: t = [2/x, 1/x, 2/x]
sage: r = full_group_by([0,1,2], key=lambda i:t[i])
sage: sorted(r, key=lambda p:p[1])
[(2/x, [0, 2]), (1/x, [1])]
sage: from itertools import groupby
sage: for k, elements in groupby(sorted([0,1,2],
....: key=lambda i:t[i]),
....: key=lambda i:t[i]):
....: print k, list(elements)
2/x [0]
1/x [1]
2/x [2]
Note that the behavior is different from itertools.groupby because neither \(1/x<2/x\) nor \(2/x<1/x\) does hold.
Here, the result r has been sorted in order to guarantee a consistent order for the doctest suite.
Tests whether or not FSM inherits from Automaton.
TESTS:
sage: from sage.combinat.finite_state_machine import is_FiniteStateMachine, is_Automaton
sage: is_Automaton(FiniteStateMachine())
False
sage: is_Automaton(Automaton())
True
sage: is_FiniteStateMachine(Automaton())
True
Tests whether or not PI inherits from FSMProcessIterator.
TESTS:
sage: from sage.combinat.finite_state_machine import is_FSMProcessIterator, FSMProcessIterator
sage: is_FSMProcessIterator(FSMProcessIterator(FiniteStateMachine()))
Traceback (most recent call last):
...
ValueError: No state is initial.
Tests whether or not S inherits from FSMState.
TESTS:
sage: from sage.combinat.finite_state_machine import is_FSMState, FSMState
sage: is_FSMState(FSMState('A'))
True
Tests whether or not T inherits from FSMTransition.
TESTS:
sage: from sage.combinat.finite_state_machine import is_FSMTransition, FSMTransition
sage: is_FSMTransition(FSMTransition('A', 'B'))
True
Tests whether or not FSM inherits from FiniteStateMachine.
TESTS:
sage: from sage.combinat.finite_state_machine import is_FiniteStateMachine
sage: is_FiniteStateMachine(FiniteStateMachine())
True
sage: is_FiniteStateMachine(Automaton())
True
sage: is_FiniteStateMachine(Transducer())
True
Tests whether or not FSM inherits from Transducer.
TESTS:
sage: from sage.combinat.finite_state_machine import is_FiniteStateMachine, is_Transducer
sage: is_Transducer(FiniteStateMachine())
False
sage: is_Transducer(Transducer())
True
sage: is_FiniteStateMachine(Transducer())
True
This function adds the package tikz with support for automata to the preamble of Latex so that the finite state machines can be drawn nicely.
INPUT:
Nothing.
OUTPUT:
Nothing.
TESTS:
sage: from sage.combinat.finite_state_machine import setup_latex_preamble
sage: setup_latex_preamble()