Finite State Machines, Automata, Transducers

This module adds support for finite state machines, automata and transducers. See classes Automaton and Transducer (or the more general class FiniteStateMachine) and the examples below for details creating one.

Contents

FiniteStateMachine and derived classes Transducer and Automaton

Accessing parts of a finite state machine

state() Get a state by its label
states() List of states
iter_states() Iterator over the states
initial_states() List of initial states
iter_initial_states() Iterator over initial states
final_states() List of final states
iter_final_states() Iterator over final states
transition() Get a transition by its states and labels
transitions() List of transitions
iter_transitions() Iterator over the transitions
predecessors() List of predecessors of a state
induced_sub_finite_state_machine() Induced sub-machine
accessible_components() Accessible components
final_components() Final components (connected components which cannot be left again)

(Modified) Copies

empty_copy() Returns an empty deep copy
deepcopy() Returns a deep copy
relabeled() Returns a relabeled deep copy

Manipulation

add_state() Add a state
add_states() Add states
delete_state() Delete a state
add_transition() Add a transition
add_transitions_from_function() Add transitions
on_duplicate_transition Hook for handling duplicate transitions
add_from_transition_function() Add transitions by a transition function
delete_transition() Delete a transition
remove_epsilon_transitions() Remove epsilon transitions (not implemented)
split_transitions() Split transitions with input words of length > 1
determine_alphabets() Determines input and output alphabets
construct_final_word_out() Construct final output by implicitly reading trailing letters; cf. with_final_word_out()

Properties

has_state() Checks for a state
has_initial_state() Checks for an initial state
has_initial_states() Checks for initial states
has_final_state() Checks for an final state
has_final_states() Checks for final states
has_transition() Checks for a transition
is_deterministic() Checks for a deterministic machine
is_complete() Checks for a complete machine
is_connected() Checks for a connected machine
is_Markov_chain() Checks for a Markov chain
is_monochromatic() Checks whether the colors of all states are equal
asymptotic_moments() Main terms of expectation and variance of sums of labels
epsilon_successors() Epsilon successors of a state

Operations

disjoint_union() Disjoint union (not implemented)
concatenation() Concatenation (not implemented)
Kleene_closure() Kleene closure (not implemented)
Automaton.intersection() Intersection of automata
Transducer.intersection() Intersection of transducers
Transducer.cartesian_product() Cartesian product of a transducer with another finite state machine
product_FiniteStateMachine() Product of finite state machines
composition() Composition (output of other is input of self)
__call__() Composition with other finite state machine
input_projection() Input projection (output is deleted)
output_projection() Output projection (old output is new input)
projection() Input or output projection
transposition() Transposition (all transitions are reversed)
with_final_word_out() Machine with final output constructed by implicitly reading trailing letters, cf. construct_final_word_out() for inplace version
Automaton.determinisation() Determinisation of an automaton
process() Process input
__call__() Process input with shortened output
Automaton.process() Process input of an automaton (output differs from general case)
Transducer.process() Process input of a transducer (output differs from general case)
iter_process() Return process iterator

Simplification

prepone_output() Prepone output where possible
equivalence_classes() List of equivalent states
quotient() Quotient with respect to equivalence classes
merged_transitions() Merge transitions while adding input
markov_chain_simplification() Simplification of a Markov chain
Automaton.minimization() Minimization of an automaton
Transducer.simplification() Simplification of a transducer

Conversion

adjacency_matrix() (Weighted) adjacency matrix
graph() Underlying DiGraph
plot() Plot
LaTeX output
latex_options() Set options
set_coordinates() Set coordinates of the states
default_format_transition_label() Default formatting of words in transition labels
format_letter_negative() Format negative numbers as overlined number
format_transition_label_reversed() Format words in transition labels in reversed order

FSMState

final_word_out Final output of a state
is_final Describes whether a state is final or not
is_initial Describes whether a state is initial or not
label() Label of a state
relabeled() Returns a relabeled deep copy of a state
fully_equal() Checks whether two states are fully equal (including all attributes)

FSMTransition

from_state State in which transition starts
to_state State in which transition ends
word_in Input word of the transition
word_out Output word of the transition
deepcopy() Returns a deep copy of the transition

FSMProcessIterator

next() Makes one step in processing the input tape
preview_word() Reads a word from the input tape
result() Returns the finished branches during process

Helper Functions

equal() Checks whether all elements of iterator are equal
full_group_by() Group iterable by values of some key
startswith() Determine whether list starts with the given prefix
FSMLetterSymbol() Returns a string associated to the input letter
FSMWordSymbol() Returns a string associated to a word
is_FSMState() Tests whether an object inherits from FSMState
is_FSMTransition() Tests whether an object inherits from FSMTransition
is_FiniteStateMachine() Tests whether an object inherits from FiniteStateMachine
duplicate_transition_ignore() Default function for handling duplicate transitions
duplicate_transition_raise_error() Raise error when inserting a duplicate transition
duplicate_transition_add_input() Add input when inserting a duplicate transition

Examples

We start with a general FiniteStateMachine. Later there will be also an Automaton and a Transducer.

A simple finite state machine

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 and add some states and transitions:

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)

Let us look at sunset more closely:

sage: sunset
Transition from 'day' to 'night': -|-

Note that could also have created and added the transitions directly by:

sage: fsm.add_transition('day', 'night')
Transition from 'day' to 'night': -|-

This would have had added the states automatically, since they are present in the transitions.

Anyhow, we got the following finite state machine:

sage: fsm
Finite state machine with 2 states

We can also obtain the underlying directed graph by

sage: fsm.graph()
Digraph on 2 vertices

To visualize a finite state machine, we can use latex() and run the result through LaTeX, see the section on LaTeX output below.

Alternatively, we could have created the finite state machine above simply by

sage: FiniteStateMachine([('night', 'day'), ('day', 'night')])
Finite state machine with 2 states

See FiniteStateMachine for a lot of possibilities to create finite state machines.

A simple Automaton (recognizing NAFs)

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: sage.combinat.finite_state_machine.FSMOldProcessOutput = False  # activate new output behavior
sage: NAF([0])
True
sage: NAF([0, 1])
True
sage: NAF([1, -1])
False
sage: NAF([0, -1, 0, 1])
True
sage: NAF([0, -1, -1, -1, 0])
False
sage: NAF([-1, 0, 0, 1, 1])
False

Alternatively, we could call that by

sage: NAF.process([0, -1, 0, 1])
(True, 'B')

which gives additionally the state in which we arrived.

LaTeX output

We can visualize a finite state machine by converting it to LaTeX by using the usual function latex(). Within LaTeX, TikZ is used for typesetting the graphics, see the Wikipedia article PGF/TikZ.

sage: print latex(NAF)
\begin{tikzpicture}[auto, initial text=, >=latex]
\node[state, accepting, initial] (v0) at (3.000000, 0.000000) {$\text{\texttt{A}}$};
\node[state, accepting] (v1) at (-3.000000, 0.000000) {$\text{\texttt{B}}$};
\path[->] (v0) edge[loop above] node {$0$} ();
\path[->] (v0.185.00) edge node[rotate=360.00, anchor=north] {$1, -1$} (v1.355.00);
\path[->] (v1.5.00) edge node[rotate=0.00, anchor=south] {$0$} (v0.175.00);
\end{tikzpicture}

We can turn this into a graphical representation.

sage: view(NAF) # not tested

To actually see this, use the live documentation in the Sage notebook and execute the cells in this and the previous section.

Several options can be set to customize the output, see latex_options() for details. In particular, we use format_letter_negative() to format \(-1\) as \(\overline{1}\).

sage: NAF.latex_options(
....:     coordinates={'A': (0, 0),
....:                  'B': (6, 0)},
....:     initial_where={'A': 'below'},
....:     format_letter=NAF.format_letter_negative,
....:     format_state_label=lambda x:
....:         r'\mathcal{%s}' % x.label()
....: )
sage: print latex(NAF)
\begin{tikzpicture}[auto, initial text=, >=latex]
\node[state, accepting, initial, initial where=below] (v0) at (0.000000, 0.000000) {$\mathcal{A}$};
\node[state, accepting] (v1) at (6.000000, 0.000000) {$\mathcal{B}$};
\path[->] (v0) edge[loop above] node {$0$} ();
\path[->] (v0.5.00) edge node[rotate=0.00, anchor=south] {$1, \overline{1}$} (v1.175.00);
\path[->] (v1.185.00) edge node[rotate=360.00, anchor=north] {$0$} (v0.355.00);
\end{tikzpicture}
sage: view(NAF) # not tested

A simple transducer (binary inverter)

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])
[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.

A transducer which performs division by \(3\) in binary

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)

which assumes reading a binary number from left to right. We get the transducer with

sage: D = Transducer(f, initial_states=[0], final_states=[0],
....:                input_alphabet=[0, 1])

Let us try to divide \(12\) by \(3\):

sage: D([1, 1, 0, 0])
[0, 1, 0, 0]

Now we want to divide \(13\) by \(3\):

sage: D([1, 1, 0, 1])
Traceback (most recent call last):
...
ValueError: Invalid input sequence.

The raised ValueError means \(13\) is not divisible by \(3\).

Gray Code

The Gray code is a binary numeral system where two successive values differ in only one bit, cf. the Wikipedia article Gray_code. The Gray code of an integer \(n\) is obtained by a bitwise xor between the binary expansion of \(n\) and the binary expansion of \(\lfloor n/2\rfloor\); the latter corresponds to a shift by one position in binary.

The purpose of this example is to construct a transducer converting the standard binary expansion to the Gray code by translating this construction into operations with transducers.

For this construction, the least significant digit is at the left-most position. Note that it is easier to shift everything to the right first, i.e., multiply by \(2\) instead of building \(\lfloor n/2\rfloor\). Then, we take the input xor with the right shift of the input and forget the first letter.

We first construct a transducer shifting the binary expansion to the right. This requires storing the previously read digit in a state.

sage: def shift_right_transition(state, digit):
....:     if state == 'I':
....:         return (digit, None)
....:     else:
....:         return (digit, state)
sage: shift_right_transducer = Transducer(
....:     shift_right_transition,
....:     initial_states=['I'],
....:     input_alphabet=[0, 1],
....:     final_states=[0])
sage: shift_right_transducer.transitions()
[Transition from 'I' to 0: 0|-,
 Transition from 'I' to 1: 1|-,
 Transition from 0 to 0: 0|0,
 Transition from 0 to 1: 1|0,
 Transition from 1 to 0: 0|1,
 Transition from 1 to 1: 1|1]
sage: sage.combinat.finite_state_machine.FSMOldProcessOutput = False
sage: shift_right_transducer([0, 1, 1, 0])
[0, 1, 1]
sage: shift_right_transducer([1, 0, 0])
[1, 0]

The output of the shifts above look a bit weird (from a right-shift transducer, we would expect, for example, that [1, 0, 0] was mapped to [0, 1, 0]), since we write None instead of the zero at the left. Further, note that only \(0\) is listed as a final state as we have to enforce that a most significant zero is read as the last input letter in order to flush the last digit:

sage: shift_right_transducer([0, 1, 0, 1])
Traceback (most recent call last):
...
ValueError: Invalid input sequence.

Next, we construct the transducer performing the xor operation. We also have to take None into account as our shift_right_transducer waits one iteration until it starts writing output. This corresponds with our intention to forget the first letter.

sage: def xor_transition(state, digits):
....:    if digits[0] is None or digits[1] is None:
....:        return (0, None)
....:    else:
....:        return (0, digits[0].__xor__(digits[1]))
sage: from itertools import product
sage: xor_transducer = Transducer(
....:    xor_transition,
....:    initial_states=[0],
....:    final_states=[0],
....:    input_alphabet=list(product([None, 0, 1], [0, 1])))
sage: xor_transducer.transitions()
[Transition from 0 to 0: (None, 0)|-,
 Transition from 0 to 0: (None, 1)|-,
 Transition from 0 to 0: (0, 0)|0,
 Transition from 0 to 0: (0, 1)|1,
 Transition from 0 to 0: (1, 0)|1,
 Transition from 0 to 0: (1, 1)|0]
sage: xor_transducer([(None, 0), (None, 1), (0, 0), (0, 1), (1, 0), (1, 1)])
[0, 1, 1, 0]
sage: xor_transducer([(0, None)])
Traceback (most recent call last):
...
ValueError: Invalid input sequence.

The transducer computing the Gray code is then constructed as a cartesian product between the shifted version and the original input (represented here by the shift_right_transducer and the identity transducer, respectively). This cartesian product is then fed into the xor_transducer as a composition of transducers.

As described in Transducer.cartesian_product(), we have to temporarily set finite_state_machine.FSMOldCodeTransducerCartesianProduct to False in order to disable backwards compatible code.

sage: sage.combinat.finite_state_machine.FSMOldCodeTransducerCartesianProduct = False
sage: product_transducer = shift_right_transducer.cartesian_product(transducers.Identity([0, 1]))
sage: sage.combinat.finite_state_machine.FSMOldCodeTransducerCartesianProduct = True
sage: Gray_transducer = xor_transducer(product_transducer)

We use construct_final_word_out() to make sure that all output is written; otherwise, we would have to make sure that a sufficient number of trailing zeros is read.

sage: Gray_transducer.construct_final_word_out([0])
sage: Gray_transducer.transitions()
[Transition from (('I', 0), 0) to ((0, 0), 0): 0|-,
 Transition from (('I', 0), 0) to ((1, 0), 0): 1|-,
 Transition from ((0, 0), 0) to ((0, 0), 0): 0|0,
 Transition from ((0, 0), 0) to ((1, 0), 0): 1|1,
 Transition from ((1, 0), 0) to ((0, 0), 0): 0|1,
 Transition from ((1, 0), 0) to ((1, 0), 0): 1|0]

There is a prepackaged transducer for Gray code, let’s see whether they agree. We have to use relabeled() to relabel our states with integers.

sage: constructed = Gray_transducer.relabeled()
sage: packaged = transducers.GrayCode()
sage: constructed == packaged
True

Finally, we check that this indeed computes the Gray code of the first 10 non-negative integers.

sage: for n in srange(10):
....:     Gray_transducer(n.bits())
[]
[1]
[1, 1]
[0, 1]
[0, 1, 1]
[1, 1, 1]
[1, 0, 1]
[0, 0, 1]
[0, 0, 1, 1]
[1, 0, 1, 1]

Using the hook-functions

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(process, state, output):
....:     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], check_epsilon_transitions=False)
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.

Warning

The hooks of the states are also called while exploring the epsilon successors of a state (during processing). In the example above, we used check_epsilon_transitions=False to avoid this (and also therefore got a cleaner output).

Warning

The arguments used when calling a hook have changed in trac ticket #16538 from hook(state, process) to hook(process, state, output). If you are using an old-style hook, a deprecation warning is displayed.

Detecting sequences with same number of \(0\) and \(1\)

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 = FiniteStateMachine()
sage: def update_counter(process, state, output):
....:     l = process.preview_word()
....:     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])

See also methods Automaton.process() and Transducer.process() (or even FiniteStateMachine.process()), the explanation of the parameter hook and the examples in FSMState and FSMTransition, and the description and examples in FSMProcessIterator for more information on processing and hooks.

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

  • Clemens Heuberger (2013-11-03): output (labels) of determinisation,

    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

  • Daniel Krenn (2013-11-11): comments from trac #15078 included:

    docstring of FiniteStateMachine rewritten, Automaton and Transducer inherited from FiniteStateMachine

  • Daniel Krenn (2013-11-25): documentation improved according to

    comments from trac #15078

  • Clemens Heuberger, Daniel Krenn, Sara Kropf (2014-02-21–2014-07-18): A huge bunch of improvements. Details see #15841, #15847, #15848, #15849, #15850, #15922, #15923, #15924, #15925, #15928, #15960, #15961, #15962, #15963, #15975, #16016, #16024, #16061, #16128, #16132, #16138, #16139, #16140, #16143, #16144, #16145, #16146, #16191, #16200, #16205, #16206, #16207, #16229, #16253, #16254, #16255, #16266, #16355, #16357, #16387, #16425, #16539, #16555, #16557, #16588, #16589, #16666, #16668, #16674, #16675, #16677.

ACKNOWLEDGEMENT:

  • Clemens Heuberger, Daniel Krenn and Sara Kropf are supported by the Austrian Science Fund (FWF): P 24644-N26.

Methods

class sage.combinat.finite_state_machine.Automaton(*args, **kwargs)

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])
True
sage: A([1, 1, 0])
True
sage: A([1, 0, 1])
False

Note that the full output of the commands can be obtained by calling process() and looks like this:

sage: A.process([1, 0, 1])
(False, 'P')

TESTS:

sage: Automaton()
Automaton with 0 states
cartesian_product(other, only_accessible_components=True)

Returns a new automaton which accepts an input if it is accepted by both given automata.

INPUT:

OUTPUT:

A new automaton which computes the intersection (see below) of the languages 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, D, a)\) in the old automata.

The methods intersection() and cartesian_product() are the same (for 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', 0),
....:                   ('B', 'B', 0),
....:                   ('B', 'A', 1)],
....:                  initial_states=['A'],
....:                  final_states=['B'],
....:                  determine_alphabets=True)
sage: res = aut1.intersection(aut2)
sage: (aut1([1, 1]), aut2([1, 1]), res([1, 1]))
(True, False, False)
sage: (aut1([1, 0]), aut2([1, 0]), res([1, 0]))
(True, True, True)
sage: res.transitions()
[Transition from ('1', 'A') to ('2', 'A'): 1|-,
 Transition from ('2', 'A') to ('2', 'B'): 0|-,
 Transition from ('2', 'A') to ('2', 'A'): 1|-,
 Transition from ('2', 'B') to ('2', 'B'): 0|-,
 Transition from ('2', 'B') to ('2', 'A'): 1|-]

For automata with epsilon-transitions, intersection is not well defined. But for any finite state machine, epsilon-transitions can be removed by remove_epsilon_transitions().

sage: a1 = Automaton([(0, 0, 0),
....:                 (0, 1, None),
....:                 (1, 1, 1),
....:                 (1, 2, 1)],
....:                 initial_states=[0],
....:                 final_states=[1],
....:                 determine_alphabets=True)
sage: a2 = Automaton([(0, 0, 0), (0, 1, 1), (1, 1, 1)],
....:                 initial_states=[0],
....:                 final_states=[1],
....:                 determine_alphabets=True)
sage: a1.intersection(a2)
Traceback (most recent call last):
...
ValueError: An epsilon-transition (with empty input)
was found.
sage: a1.remove_epsilon_transitions()  # not tested (since not implemented yet)
sage: a1.intersection(a2)  # not tested
determinisation()

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 color of a new state is the frozenset of colors of the constituent states of self. Therefore, the colors of the constituent states have to be hashable.

The input alphabet must be specified.

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'])]
sage: A = Automaton([(0, 1, 1), (0, 2, [1, 1]), (0, 3, [1, 1, 1]),
....:                (1, 0, -1), (2, 0, -2), (3, 0, -3)],
....:               initial_states=[0], final_states=[0, 1, 2, 3])
sage: B = A.determinisation().relabeled()
sage: all(t.to_state.label() == 2 for t in
....:     B.state(2).transitions)
True
sage: B.state(2).is_final
False
sage: B.delete_state(2)  # this is a sink
sage: sorted(B.transitions())
[Transition from 0 to 1: 1|-,
 Transition from 1 to 0: -1|-,
 Transition from 1 to 3: 1|-,
 Transition from 3 to 0: -2|-,
 Transition from 3 to 4: 1|-,
 Transition from 4 to 0: -3|-]

Note that colors of states have to be hashable:

sage: A = Automaton([[0, 0, 0]], initial_states=[0])
sage: A.state(0).color = []
sage: A.determinisation()
Traceback (most recent call last):
...
TypeError: unhashable type: 'list'
sage: A.state(0).color = ()
sage: A.determinisation()
Automaton with 1 states

TESTS:

This is from trac ticket #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'), (True, 'C')]
sage: auto.states()
['A', 'C', 'B']
sage: Ddet = auto.determinisation()
sage: Ddet
Automaton with 3 states
sage: Ddet.is_deterministic()
True
sage: sorted(Ddet.transitions())
[Transition from frozenset(['A']) to frozenset(['A', 'B']): 'a'|-,
 Transition from frozenset(['A']) to frozenset(['A']): 'b'|-,
 Transition from frozenset(['A', 'B']) to frozenset(['A', 'B']): 'a'|-,
 Transition from frozenset(['A', 'B']) to frozenset(['A', 'C']): 'b'|-,
 Transition from frozenset(['A', 'C']) to frozenset(['A', 'B']): 'a'|-,
 Transition from frozenset(['A', 'C']) to frozenset(['A']): 'b'|-]
sage: Ddet.initial_states()
[frozenset(['A'])]
sage: Ddet.final_states()
[frozenset(['A', 'C'])]
sage: Ddet.process(list('aaab'))
(True, frozenset(['A', 'C']))
intersection(other, only_accessible_components=True)

Returns a new automaton which accepts an input if it is accepted by both given automata.

INPUT:

OUTPUT:

A new automaton which computes the intersection (see below) of the languages 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, D, a)\) in the old automata.

The methods intersection() and cartesian_product() are the same (for 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', 0),
....:                   ('B', 'B', 0),
....:                   ('B', 'A', 1)],
....:                  initial_states=['A'],
....:                  final_states=['B'],
....:                  determine_alphabets=True)
sage: res = aut1.intersection(aut2)
sage: (aut1([1, 1]), aut2([1, 1]), res([1, 1]))
(True, False, False)
sage: (aut1([1, 0]), aut2([1, 0]), res([1, 0]))
(True, True, True)
sage: res.transitions()
[Transition from ('1', 'A') to ('2', 'A'): 1|-,
 Transition from ('2', 'A') to ('2', 'B'): 0|-,
 Transition from ('2', 'A') to ('2', 'A'): 1|-,
 Transition from ('2', 'B') to ('2', 'B'): 0|-,
 Transition from ('2', 'B') to ('2', 'A'): 1|-]

For automata with epsilon-transitions, intersection is not well defined. But for any finite state machine, epsilon-transitions can be removed by remove_epsilon_transitions().

sage: a1 = Automaton([(0, 0, 0),
....:                 (0, 1, None),
....:                 (1, 1, 1),
....:                 (1, 2, 1)],
....:                 initial_states=[0],
....:                 final_states=[1],
....:                 determine_alphabets=True)
sage: a2 = Automaton([(0, 0, 0), (0, 1, 1), (1, 1, 1)],
....:                 initial_states=[0],
....:                 final_states=[1],
....:                 determine_alphabets=True)
sage: a1.intersection(a2)
Traceback (most recent call last):
...
ValueError: An epsilon-transition (with empty input)
was found.
sage: a1.remove_epsilon_transitions()  # not tested (since not implemented yet)
sage: a1.intersection(a2)  # not tested
minimization(algorithm=None)

Returns the minimization of the input automaton as a new automaton.

INPUT:

  • algorithm – Either Moore’s algorithm (by algorithm='Moore' or as default for deterministic automata) or Brzozowski’s algorithm (when algorithm='Brzozowski' or when the automaton is not deterministic) is used.

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
process(*args, **kwargs)

Warning

The default output of this method is scheduled to change. This docstring describes the new default behaviour, which can already be achieved by setting FSMOldProcessOutput to False.

Returns whether the automaton accepts the input and the state where the computation stops.

INPUT:

  • input_tape – the input tape can be a list or an iterable with entries from the input alphabet. If we are working with a multi-tape machine (see parameter use_multitape_input and notes below), then the tape is a list or tuple of tracks, each of which can be a list or an iterable with entries from the input alphabet.
  • initial_state or initial_states – the initial state(s) in which the machine starts. Either specify a single one with initial_state or a list of them with initial_states. If both are given, initial_state will be appended to initial_states. If neither is specified, the initial states of the finite state machine are taken.
  • list_of_outputs – (default: None) a boolean or None. If True, then the outputs are given in list form (even if we have no or only one single output). If False, then the result is never a list (an exception is raised if the result cannot be returned). If list_of_outputs=None the method determines automatically what to do (e.g. if a non-deterministic machine returns more than one path, then the output is returned in list form).
  • only_accepted – (default: False) a boolean. If set, then the first argument in the output is guaranteed to be True (if the output is a list, then the first argument of each element will be True).
  • full_output – (default: True) a boolean. If set, then the full output is given, otherwise only whether the sequence is accepted or not (the first entry below only).
  • always_include_output – if set (not by default), always return a triple containing the (non-existing) output. This is in order to obtain output compatible with that of FiniteStateMachine.process(). If this parameter is set, full_output has no effect.
  • format_output – a function that translates the written output (which is in form of a list) to something more readable. By default (None) identity is used here.
  • check_epsilon_transitions – (default: True) a boolean. If False, then epsilon transitions are not taken into consideration during process.
  • write_final_word_out – (default: True) a boolean specifying whether the final output words should be written or not.
  • use_multitape_input – (default: False) a boolean. If True, then the multi-tape mode of the process iterator is activated. See also the notes below for multi-tape machines.

OUTPUT:

The full output is a pair (or a list of pairs, cf. parameter list_of_outputs), where

  • the first entry is True if the input string is accepted and
  • the second gives the state reached after processing the input tape (This is a state with label None if the input could not be processed, i.e., if at one point no transition to go on could be found.).

If full_output is False, then only the first entry is returned.

If always_include_output is set, an additional third entry [] is included.

Note that in the case the automaton is not deterministic, all possible paths are taken into account. You can use determinisation() to get a deterministic automaton machine.

By setting FSMOldProcessOutput to False the new desired output is produced.

This function uses an iterator which, in its simplest form, goes from one state to another in each step. To decide which way to go, it uses the input words of the outgoing transitions and compares them to the input tape. More precisely, in each step, the iterator takes an outgoing transition of the current state, whose input label equals the input letter of the tape.

If the choice of the outgoing transition is not unique (i.e., we have a non-deterministic finite state machine), all possibilites are followed. This is done by splitting the process into several branches, one for each of the possible outgoing transitions.

The process (iteration) stops if all branches are finished, i.e., for no branch, there is any transition whose input word coincides with the processed input tape. This can simply happen when the entire tape was read.

Also see __call__() for a version of process() with shortened output.

Internally this function creates and works with an instance of FSMProcessIterator. This iterator can also be obtained with iter_process().

If working with multi-tape finite state machines, all input words of transitions are words of \(k\)-tuples of letters. Moreover, the input tape has to consist of \(k\) tracks, i.e., be a list or tuple of \(k\) iterators, one for each track.

Warning

Working with multi-tape finite state machines is still experimental and can lead to wrong outputs.

EXAMPLES:

In the following examples, we construct an automaton which accepts non-adjacent forms (see also the example on non-adjacent forms in the documentation of the module finite_state_machine) and then test it by feeding it with several binary digit expansions.

sage: sage.combinat.finite_state_machine.FSMOldProcessOutput = False  # activate new output behavior
sage: NAF = Automaton(
....:     {'_': [('_', 0), ('1', 1)], '1': [('_', 0)]},
....:     initial_states=['_'], final_states=['_', '1'])
sage: [NAF.process(w) for w in [[0], [0, 1], [1, 1], [0, 1, 0, 1],
....:                           [0, 1, 1, 1, 0], [1, 0, 0, 1, 1]]]
[(True, '_'), (True, '1'), (False, None),
 (True, '1'), (False, None), (False, None)]

If we just want a condensed output, we use:

sage: [NAF.process(w, full_output=False)
....:     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]

It is equivalent to:

sage: [NAF(w) 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]

The following example illustrates the difference between non-existing paths and reaching a non-final state:

sage: NAF.process([2])
(False, None)
sage: NAF.add_transition(('_', 's', 2))
Transition from '_' to 's': 2|-
sage: NAF.process([2])
(False, 's')

A simple example of a (non-deterministic) multi-tape automaton is the following: It checks whether the two input tapes have the same number of ones:

sage: M = Automaton([('=', '=', (1, 1)),
....:                ('=', '=', (None, 0)),
....:                ('=', '=', (0, None)),
....:                ('=', '<', (None, 1)),
....:                ('<', '<', (None, 1)),
....:                ('<', '<', (None, 0)),
....:                ('=', '>', (1, None)),
....:                ('>', '>', (1, None)),
....:                ('>', '>', (0, None))],
....:               initial_states=['='],
....:               final_states=['='])
sage: M.process(([1, 0, 1], [1, 0]), use_multitape_input=True)
(False, '>')
sage: M.process(([0, 1, 0], [0, 1, 1]), use_multitape_input=True)
(False, '<')
sage: M.process(([1, 1, 0, 1], [0, 0, 1, 0, 1, 1]),
....:           use_multitape_input=True)
(True, '=')

Alternatively, we can use the following (non-deterministic) multi-tape automaton for the same check:

sage: N = Automaton([('=', '=', (0, 0)),
....:                ('=', '<', (None, 1)),
....:                ('<', '<', (0, None)),
....:                ('<', '=', (1, None)),
....:                ('=', '>', (1, None)),
....:                ('>', '>', (None, 0)),
....:                ('>', '=', (None, 1))],
....:               initial_states=['='],
....:               final_states=['='])
sage: N.process(([1, 0, 1], [1, 0]), use_multitape_input=True)
(False, '>')
sage: N.process(([0, 1, 0], [0, 1, 1]), use_multitape_input=True)
(False, '<')
sage: N.process(([1, 1, 0, 1], [0, 0, 1, 0, 1, 1]),
....:           use_multitape_input=True)
(True, '=')
sage.combinat.finite_state_machine.FSMLetterSymbol(letter)

Returns a string associated to the input letter.

INPUT:

  • letter – the input letter or None (representing the empty word).

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)
'-'
class sage.combinat.finite_state_machine.FSMProcessIterator(fsm, input_tape=None, initial_state=None, initial_states=, []use_multitape_input=False, check_epsilon_transitions=True, write_final_word_out=True, format_output=None, **kwargs)

Bases: sage.structure.sage_object.SageObject, _abcoll.Iterator

This class takes an input, feeds it into a finite state machine (automaton or transducer, in particular), tests whether this was successful and calculates the written output.

INPUT:

  • fsm – the finite state machine on which the input should be processed.
  • input_tape – the input tape can be a list or an iterable with entries from the input alphabet. If we are working with a multi-tape machine (see parameter use_multitape_input and notes below), then the tape is a list or tuple of tracks, each of which can be a list or an iterable with entries from the input alphabet.
  • initial_state or initial_states – the initial state(s) in which the machine starts. Either specify a single one with initial_state or a list of them with initial_states. If both are given, initial_state will be appended to initial_states. If neither is specified, the initial states of the finite state machine are taken.
  • format_output – a function that translates the written output (which is in form of a list) to something more readable. By default (None) identity is used here.
  • check_epsilon_transitions – (default: True) a boolean. If False, then epsilon transitions are not taken into consideration during process.
  • write_final_word_out – (default: True) a boolean specifying whether the final output words should be written or not.
  • use_multitape_input – (default: False) a boolean. If True, then the multi-tape mode of the process iterator is activated. See also the notes below for multi-tape machines.

OUTPUT:

An iterator.

In its simplest form, it behaves like an iterator which, in each step, goes from one state to another. To decide which way to go, it uses the input words of the outgoing transitions and compares them to the input tape. 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.

If the choice of the outgoing transition is not unique (i.e., we have a non-deterministic finite state machine), all possibilites are followed. This is done by splitting the process into several branches, one for each of the possible outgoing transitions.

The process (iteration) stops if all branches are finished, i.e., for no branch, there is any transition whose input word coincides with the processed input tape. This can simply happen when the entire tape was read. When the process stops, a StopIteration exception is thrown.

Warning

Processing an input tape of length \(n\) usually takes at least \(n+1\) iterations, since there will be \(n+1\) states visited (in the case the taken transitions have input words consisting of single letters).

An instance of this class is generated when FiniteStateMachine.process() or FiniteStateMachine.iter_process() of a finite state machine, an automaton, or a transducer is invoked.

When working with multi-tape finite state machines, all input words of transitions are words of \(k\)-tuples of letters. Moreover, the input tape has to consist of \(k\) tracks, i.e., be a list or tuple of \(k\) iterators, one for each track.

Warning

Working with multi-tape finite state machines is still experimental and can lead to wrong outputs.

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() (internally) uses a 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 current in it:
....:     print current
process (1 branch)
+ at state 'B'
+-- tape at 1, [[]]
process (1 branch)
+ at state 'B'
+-- tape at 2, [[]]
process (1 branch)
+ at state 'A'
+-- tape at 3, [[1, 0]]
process (1 branch)
+ at state 'A'
+-- tape at 4, [[1, 0, 0]]
process (1 branch)
+ at state 'B'
+-- tape at 5, [[1, 0, 0]]
process (1 branch)
+ at state 'A'
+-- tape at 6, [[1, 0, 0, 1, 0]]
process (1 branch)
+ at state 'B'
+-- tape at 7, [[1, 0, 0, 1, 0]]
process (1 branch)
+ at state 'B'
+-- tape at 8, [[1, 0, 0, 1, 0]]
process (1 branch)
+ at state 'B'
+-- tape at 9, [[1, 0, 0, 1, 0]]
process (1 branch)
+ at state 'A'
+-- tape at 10, [[1, 0, 0, 1, 0, 1, 0]]
process (0 branches)
sage: it.result()
[(True, 'A', [1, 0, 0, 1, 0, 1, 0])]
sage: T = Transducer([(0, 0, 0, 'a'), (0, 1, 0, 'b'),
....:                 (1, 2, 1, 'c'), (2, 0, 0, 'd'),
....:                 (2, 1, None, 'd')],
....:                initial_states=[0], final_states=[2])
sage: T.process([0, 0, 1], format_output=lambda o: ''.join(o))
[(False, 1, 'abcd'), (True, 2, 'abc')]
sage: it = FSMProcessIterator(T, input_tape=[0, 0, 1],
....:                         format_output=lambda o: ''.join(o))
sage: for current in it:
....:     print current
process (2 branches)
+ at state 0
+-- tape at 1, [['a']]
+ at state 1
+-- tape at 1, [['b']]
process (2 branches)
+ at state 0
+-- tape at 2, [['a', 'a']]
+ at state 1
+-- tape at 2, [['a', 'b']]
process (2 branches)
+ at state 1
+-- tape at 3, [['a', 'b', 'c', 'd']]
+ at state 2
+-- tape at 3, [['a', 'b', 'c']]
process (0 branches)
sage: it.result()
[(False, 1, 'abcd'), (True, 2, 'abc')]

TESTS:

sage: T = Transducer([[0, 0, 0, 0]])
sage: T.process([])
Traceback (most recent call last):
...
ValueError: No state is initial.
sage: T = Transducer([[0, 1, 0, 0]], initial_states=[0, 1])
sage: T.process([])
[(False, 0, []), (False, 1, [])]
sage: T = Transducer([[0, 0, 0, 0]],
....:                initial_states=[0], final_states=[0])
sage: T.state(0).final_word_out = [42]
sage: T.process([0])
(True, 0, [0, 42])
sage: T.process([0], write_final_word_out=False)
(True, 0, [0])
class Current

Bases: dict

This class stores the branches which have to be processed during iteration and provides a nicer formatting of them.

This class is derived from dict. It is returned by the next-function during iteration.

EXAMPLES:

In the following example you can see the dict directly and then the nicer output provided by this class:

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: for current in it:
....:     print dict(current)
....:     print current
{((1, 0),): {'A': (tape at 1, [[1]])}}
process (1 branch)
+ at state 'A'
+-- tape at 1, [[1]]
{((2, 0),): {'A': (tape at 2, [[1, 0]])}}
process (1 branch)
+ at state 'A'
+-- tape at 2, [[1, 0]]
{}
process (0 branches)
FSMProcessIterator.accept_input

Is True if the reached state is accepted. This is only available at the end of the iteration process.

Warning

This attribute is deprecated and should not be used any longer (it may return a wrong result for non-deterministic finite state machines).

TESTS:

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.result()
[(True, 'A', [1, 0, 0])]
sage: it.accept_input
doctest:...: DeprecationWarning: This attribute will be removed
in future releases. Use result() at the end of our iteration
or the output of next().
See http://trac.sagemath.org/16538 for details.
True
FSMProcessIterator.current_state

The current/reached state in the process.

Warning

This attribute is deprecated and should not be used any longer (it may return a wrong result for non-deterministic finite state machines).

TESTS:

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 current in it:
....:     s = it.current_state
....:     print current
....:     print 'current state:', s
doctest:...: DeprecationWarning: This attribute will be
removed in future releases. Use result() at the end of our
iteration or the output of next().
See http://trac.sagemath.org/16538 for details.
process (1 branch)
+ at state 'A'
+-- tape at 1, [[1]]
current state: 'A'
process (1 branch)
+ at state 'A'
+-- tape at 2, [[1, 0]]
current state: 'A'
process (1 branch)
+ at state 'A'
+-- tape at 3, [[1, 0, 0]]
current state: 'A'
process (0 branches)
current state: None
FSMProcessIterator.next()

Makes one step in processing the input tape.

INPUT:

Nothing.

OUTPUT:

It returns the current status of the iterator (see below). A StopIteration exception is thrown when there is/was nothing to do (i.e. all branches ended with previous call of __next__()).

The current status is a dictionary (encapsulated into an instance of Current). The keys are positions on the tape. The value corresponding to such a position is again a dictionary, where each entry represents a branch of the process. This dictionary maps the current state of a branch to a pair consisting of a tape cache and a list of output words, which were written during reaching this 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: next(it)
process (1 branch)
+ at state 'A'
+-- tape at 1, [[1]]
sage: next(it)
process (1 branch)
+ at state 'A'
+-- tape at 2, [[1, 0]]
sage: next(it)
process (0 branches)
sage: next(it)
Traceback (most recent call last):
...
StopIteration

TESTS:

sage: Z = Transducer()
sage: s = Z.add_state(0)
sage: s.is_initial = True
sage: s.is_final = True
sage: s.final_word_out = [1, 2]
sage: Z.process([])
(True, 0, [1, 2])
sage: it = FSMProcessIterator(Z, input_tape=[])
sage: next(it)
process (0 branches)
sage: next(it)
Traceback (most recent call last):
...
StopIteration
sage: N = Transducer([(0, 0, 0, 1)], initial_states=[0])
sage: def h_old(state, process):
....:     print state, process
sage: N.state(0).hook = h_old
sage: N.process([0, 0])
doctest:...: DeprecationWarning: The hook of state 0 cannot
be processed: It seems that you are using an old-style hook,
which is deprecated.
See http://trac.sagemath.org/16538 for details.
(False, 0, [1, 1])
sage: def h_new(process, state, outputs):
....:     print state, outputs
sage: N.state(0).hook = h_new
sage: N.process([0, 0], check_epsilon_transitions=False)
0 [[]]
0 [[1]]
0 [[1, 1]]
(False, 0, [1, 1])
FSMProcessIterator.output_tape

The written output.

Warning

This attribute is deprecated and should not be used any longer (it may return a wrong result for non-deterministic finite state machines).

TESTS:

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 current in it:
....:     t = it.output_tape
....:     print current
....:     print 'output:', t
doctest:...: DeprecationWarning: This attribute will be removed
in future releases. Use result() at the end of our iteration
or the output of next().
See http://trac.sagemath.org/16538 for details.
process (1 branch)
+ at state 'A'
+-- tape at 1, [[1]]
output: [1]
process (1 branch)
+ at state 'A'
+-- tape at 2, [[1, 0]]
output: [1, 0]
process (1 branch)
+ at state 'A'
+-- tape at 3, [[1, 0, 0]]
output: [1, 0, 0]
process (0 branches)
output: None
FSMProcessIterator.preview_word(track_number=None, length=1, return_word=False)

Reads a word from the input tape.

INPUT:

  • track_number – an integer or None. If None, then a tuple of words (one from each track) is returned.
  • length – (default: 1) the length of the word(s).
  • return_word – (default: False) a boolean. If set, then a word is returned, otherwise a single letter (in which case length has to be 1).

OUTPUT:

A single letter or a word.

An exception StopIteration is thrown if the tape (at least one track) has reached its end.

Typically, this method is called from a hook-function of a state.

EXAMPLES:

sage: inverter = Transducer({'A': [('A', 0, 'one'),
....:                              ('A', 1, 'zero')]},
....:     initial_states=['A'], final_states=['A'])
sage: def state_hook(process, state, output):
....:     print "We are now in state %s." % (state.label(),)
....:     print "Next on the tape is a %s." % (
....:         process.preview_word(),)
sage: inverter.state('A').hook = state_hook
sage: it = inverter.iter_process(
....:     input_tape=[0, 1, 1],
....:     check_epsilon_transitions=False)
sage: for _ in it:
....:     pass
We are now in state A.
Next on the tape is a 0.
We are now in state A.
Next on the tape is a 1.
We are now in state A.
Next on the tape is a 1.
We are now in state A.
sage: it.result()
[(True, 'A', ['one', 'zero', 'zero'])]
FSMProcessIterator.result(format_output=None)

Returns the already finished branches during process.

INPUT:

  • format_output – a function converting the output from list form to something more readable (default: output the list directly).

OUTPUT:

A list of triples (accepted, state, output).

See also the parameter format_output of FSMProcessIterator.

EXAMPLES:

sage: inverter = Transducer({'A': [('A', 0, 'one'), ('A', 1, 'zero')]},
....:     initial_states=['A'], final_states=['A'])
sage: it = inverter.iter_process(input_tape=[0, 1, 1])
sage: for _ in it:
....:     pass
sage: it.result()
[(True, 'A', ['one', 'zero', 'zero'])]
sage: it.result(lambda L: ', '.join(L))
[(True, 'A', 'one, zero, zero')]

Using both the parameter format_output of FSMProcessIterator and the parameter format_output of result() leads to concatenation of the two functions:

sage: it = inverter.iter_process(input_tape=[0, 1, 1],
....:                            format_output=lambda L: ', '.join(L))
sage: for _ in it:
....:     pass
sage: it.result()
[(True, 'A', 'one, zero, zero')]
sage: it.result(lambda L: ', '.join(L))
[(True, 'A', 'o, n, e, ,,  , z, e, r, o, ,,  , z, e, r, o')]
class sage.combinat.finite_state_machine.FSMState(label, word_out=None, is_initial=False, is_final=False, final_word_out=None, hook=None, color=None, allow_label_None=False)

Bases: sage.structure.sage_object.SageObject

Class for a state of a finite state machine.

INPUT:

  • label – the label of the state.
  • word_out – (default: None) a word that is written when the state is reached.
  • is_initial – (default: False)
  • is_final – (default: False)
  • final_word_out – (default: None) a word that is written when the state is reached as the last state of some input; only for final states.
  • hook – (default: None) A function which is called when the state is reached during processing input. It takes two input parameters: the first is the current state (to allow using the same hook for several states), the second is the current process iterator object (to have full access to everything; e.g. the next letter from the input tape can be read in). It can output the next transition, i.e. the transition to take next. If it returns None the process iterator chooses. Moreover, this function can raise a StopIteration exception to stop processing of a finite state machine the input immediately. See also the example below.
  • color – (default: None) In order to distinguish states, they can be given an arbitrary “color” (an arbitrary object). This is used in FiniteStateMachine.equivalence_classes(): states of different colors are never considered to be equivalent. Note that Automaton.determinisation() requires that color is hashable.
  • allow_label_None – (default: False) If True allows also None as label. Note that a state with label None is used in FSMProcessIterator.

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

We can also define a final output word of a final state which is used if the input of a transducer leads to this state. Such final output words are used in subsequential transducers.

sage: C = FSMState('state 3', is_final=True, final_word_out='end')
sage: C.final_word_out
['end']

The final output word can be a single letter, None or a list of letters:

sage: A = FSMState('A')
sage: A.is_final = True
sage: A.final_word_out = 2
sage: A.final_word_out
[2]
sage: A.final_word_out = [2, 3]
sage: A.final_word_out
[2, 3]

Only final states can have a final output word which is not None:

sage: B = FSMState('B')
sage: B.final_word_out is None
True
sage: B.final_word_out = 2
Traceback (most recent call last):
...
ValueError: Only final states can have a final output word,
but state B is not final.

Setting the final_word_out of a final state to None is the same as setting it to [] and is also the default for a final state:

sage: C = FSMState('C', is_final=True)
sage: C.final_word_out
[]
sage: C.final_word_out = None
sage: C.final_word_out
[]
sage: C.final_word_out = []
sage: C.final_word_out
[]

It is not allowed to use None as a label:

sage: from sage.combinat.finite_state_machine import FSMState
sage: FSMState(None)
Traceback (most recent call last):
...
ValueError: Label None reserved for a special state,
choose another label.

This can be overridden by:

sage: FSMState(None, allow_label_None=True)
None

Note that Automaton.determinisation() requires that color is hashable:

sage: A = Automaton([[0, 0, 0]], initial_states=[0])
sage: A.state(0).color = []
sage: A.determinisation()
Traceback (most recent call last):
...
TypeError: unhashable type: 'list'
sage: A.state(0).color = ()
sage: A.determinisation()
Automaton with 1 states

We can use a hook function of a state to stop processing. This is done by raising a StopIteration exception. The following code demonstrates this:

sage: T = Transducer([(0, 1, 9, 'a'), (1, 2, 9, 'b'),
....:                 (2, 3, 9, 'c'), (3, 4, 9, 'd')],
....:                initial_states=[0],
....:                final_states=[4],
....:                input_alphabet=[9])
sage: def stop(process, state, output):
....:     raise StopIteration()
sage: T.state(3).hook = stop
sage: T.process([9, 9, 9, 9])
(False, 3, ['a', 'b', 'c'])
copy()

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'
deepcopy(memo=None)

Returns a deep copy of the state.

INPUT:

  • memo – (default: None) a dictionary storing already processed elements.

OUTPUT:

A new state.

EXAMPLES:

sage: from sage.combinat.finite_state_machine import FSMState
sage: A = FSMState((1, 3), color=[1, 2],
....:              is_final=True, final_word_out=3)
sage: B = deepcopy(A)
sage: B
(1, 3)
sage: B.label == A.label
True
sage: B.label is A.label
False
sage: B.color == A.color
True
sage: B.color is A.color
False
sage: B.is_final == A.is_final
True
sage: B.is_final is A.is_final
True
sage: B.final_word_out == A.final_word_out
True
sage: B.final_word_out is A.final_word_out
False
final_word_out

The final output word of a final state which is written if the state is reached as the last state of the input of the finite state machine. For a non-final state, the value is None.

final_word_out can be a single letter, a list or None, but for a final-state, it is always saved as a list.

EXAMPLES:

sage: from sage.combinat.finite_state_machine import FSMState
sage: A = FSMState('A', is_final=True, final_word_out=2)
sage: A.final_word_out
[2]
sage: A.final_word_out = 3
sage: A.final_word_out
[3]
sage: A.final_word_out = [3, 4]
sage: A.final_word_out
[3, 4]
sage: A.final_word_out = None
sage: A.final_word_out
[]
sage: B = FSMState('B')
sage: B.final_word_out is None
True

A non-final state cannot have a final output word:

sage: B.final_word_out = [3, 4]
Traceback (most recent call last):
...
ValueError: Only final states can have a final
output word, but state B is not final.
fully_equal(left, right, compare_color=True)

Checks whether two states are fully equal, i.e., including all attributes except hook.

INPUT:

  • left – a state.
  • right – a state.
  • compare_color – If True (default) colors are compared as well, otherwise not.

OUTPUT:

True or False.

Note that usual comparison by == does only compare the labels.

EXAMPLES:

sage: from sage.combinat.finite_state_machine import FSMState
sage: A = FSMState('A')
sage: B = FSMState('A', is_initial=True)
sage: A.fully_equal(B)
False
sage: A == B
True
sage: A.is_initial = True; A.color = 'green'
sage: A.fully_equal(B)
False
sage: A.fully_equal(B, compare_color=False)
True
is_final

Describes whether the state is final or not.

True if the state is final and False otherwise.

EXAMPLES:

sage: from sage.combinat.finite_state_machine import FSMState
sage: A = FSMState('A', is_final=True, final_word_out=3)
sage: A.is_final
True
sage: A.is_final = False
Traceback (most recent call last):
...
ValueError: State A cannot be non-final, because it has a
final output word. Only final states can have a final output
word.
sage: A.final_word_out = None
sage: A.is_final = False
sage: A.is_final
False
is_initial

Describes whether the state is initial.

EXAMPLES:

sage: T = Automaton([(0,0,0)])
sage: T.initial_states()
[]
sage: T.state(0).is_initial = True
sage: T.initial_states()
[0]
label()

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'
relabeled(label, memo=None)

Returns a deep copy of the state with a new label.

INPUT:

  • label – the label of new state.
  • memo – (default: None) a dictionary storing already processed elements.

OUTPUT:

A new state.

EXAMPLES:

sage: from sage.combinat.finite_state_machine import FSMState
sage: A = FSMState('A')
sage: A.relabeled('B')
'B'
class sage.combinat.finite_state_machine.FSMTransition(from_state, to_state, word_in=None, word_out=None, hook=None)

Bases: sage.structure.sage_object.SageObject

Class for a transition of a finite state machine.

INPUT:

  • from_state – state from which transition starts.
  • to_state – state in which transition ends.
  • word_in – the input word of the transitions (when the finite state machine is used as automaton)
  • word_out – the output word of the transitions (when the finite state machine is used as transducer)

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
copy()

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|-
deepcopy(memo=None)

Returns a deep copy of the transition.

INPUT:

  • memo – (default: None) a dictionary storing already processed elements.

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|-
from_state

State from which the transition starts. Read-only.

to_state

State in which the transition ends. Read-only.

word_in

Input word of the transition. Read-only.

word_out

Output word of the transition. Read-only.

sage.combinat.finite_state_machine.FSMWordSymbol(word)

Returns a string of word. It may returns the symbol of the empty word FSMEmptyWordSymbol.

INPUT:

  • word – the input word.

OUTPUT:

A string of word.

EXAMPLES:

sage: from sage.combinat.finite_state_machine import FSMWordSymbol
sage: FSMWordSymbol([0, 1, 1])
'0,1,1'
class sage.combinat.finite_state_machine.FiniteStateMachine(data=None, initial_states=None, final_states=None, input_alphabet=None, output_alphabet=None, determine_alphabets=None, with_final_word_out=None, store_states_dict=True, on_duplicate_transition=None)

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:

  • data – can be any of the following:

    1. a dictionary of dictionaries (of transitions),
    2. a dictionary of lists (of states or transitions),
    3. a list (of transitions),
    4. a function (transition function),
    5. an other instance of a finite state machine.
  • initial_states and final_states – the initial and final states of this machine

  • input_alphabet and output_alphabet – the input and output alphabets of this machine

  • determine_alphabets – If True, then the function determine_alphabets() is called after data was read and processed, if False, then not. If it is None, then it is decided during the construction of the finite state machine whether determine_alphabets() should be called.

  • with_final_word_out – If given (not None), then the function with_final_word_out() (more precisely, its inplace pendant construct_final_word_out()) is called with input letters=with_final_word_out at the end of the creation process.

  • store_states_dict – If True, then additionally the states are stored in an interal dictionary for speed up.

  • on_duplicate_transition – A function which is called when a transition is inserted into self which already existed (same from_state, same to_state, same word_in, same word_out).

    This function is assumed to take two arguments, the first being the already existing transition, the second being the new transition (as an FSMTransition). The function must return the (possibly modified) original transition.

    By default, we have on_duplicate_transition=None, which is interpreted as on_duplicate_transition=duplicate_transition_ignore, where duplicate_transition_ignore is a predefined function ignoring the occurrence. Other such predefined functions are duplicate_transition_raise_error and duplicate_transition_add_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:

  1. The input-data can be a dictionary of dictionaries, where

    • the keys of the outer dictionary are state-labels (from-states of transitions),
    • the keys of the inner dictionaries are state-labels (to-states of transitions),
    • the values of the inner dictionaries specify the transition more precisely.

    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
    
  2. 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
    
  3. 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.

  4. The input-data can also be function acting as transition function:

    This function has two input arguments:

    1. a label of a state (from which the transition starts),
    2. a letter of the (input-)alphabet (as input-label of the transition).

    It returns a tuple with the following entries:

    1. a label of a state (to which state the transition goes),
    2. a letter of or a word over the (output-)alphabet (as output-label of the transition).

    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])
    
  5. The input-data can be an other instance of a finite state machine:

    sage: FiniteStateMachine(FiniteStateMachine([]))
    Traceback (most recent call last):
    ...
    NotImplementedError
    

The following examples demonstrate the use of on_duplicate_transition:

sage: F = FiniteStateMachine([['a', 'a', 1/2], ['a', 'a', 1/2]])
sage: F.transitions()
[Transition from 'a' to 'a': 1/2|-]
sage: from sage.combinat.finite_state_machine import duplicate_transition_raise_error
sage: F1 = FiniteStateMachine([['a', 'a', 1/2], ['a', 'a', 1/2]],
....:                         on_duplicate_transition=duplicate_transition_raise_error)
Traceback (most recent call last):
...
ValueError: Attempting to re-insert transition Transition from 'a' to 'a': 1/2|-

Use duplicate_transition_add_input to emulate a Markov chain, the input labels are considered as transition probabilities:

sage: from sage.combinat.finite_state_machine import duplicate_transition_add_input
sage: F = FiniteStateMachine([['a', 'a', 1/2], ['a', 'a', 1/2]],
....:                        on_duplicate_transition=duplicate_transition_add_input)
sage: F.transitions()
[Transition from 'a' to 'a': 1|-]

Use with_final_word_out to construct final output:

sage: T = Transducer([(0, 1, 0, 0), (1, 0, 0, 0)],
....:                initial_states=[0],
....:                final_states=[0],
....:                with_final_word_out=0)
sage: for s in T.iter_final_states():
....:     print s, s.final_word_out
0 []
1 [0]

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
__call__(*args, **kwargs)

Warning

The default output of this method is scheduled to change. This docstring describes the new default behaviour, which can already be achieved by setting FSMOldProcessOutput to False.

Calls either method composition() or process() (with full_output=False). See the documentation of these functions for possible parameters.

By setting FSMOldProcessOutput to False the new desired output is produced.

EXAMPLES:

sage: sage.combinat.finite_state_machine.FSMOldProcessOutput = False  # activate new output behavior
sage: binary_inverter = Transducer({'A': [('A', 0, 1), ('A', 1, 0)]},
....:                              initial_states=['A'], final_states=['A'])
sage: binary_inverter([0, 1, 0, 0, 1, 1])
[1, 0, 1, 1, 0, 0]
sage: F = Transducer([('A', 'B', 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: H = G(F)
sage: H.states()
[('A', 1), ('B', 1), ('B', 2)]

When only one successful path is found in a non-deterministic transducer, the result of that path is returned.

sage: T = Transducer([(0, 1, 0, 1), (0, 2, 0, 2)],
....:                initial_states=[0], final_states=[1])
sage: T.process([0])
[(True, 1, [1]), (False, 2, [2])]
sage: T([0])
[1]

TESTS:

sage: F = FiniteStateMachine([(0, 1, 1, 'a'), (0, 2, 2, 'b')],
....:                        initial_states=[0],
....:                        final_states=[1])
sage: A = Automaton([(0, 1, 1), (0, 2, 2)],
....:               initial_states=[0],
....:               final_states=[1])
sage: T = Transducer([(0, 1, 1, 'a'), (0, 2, 2, 'b')],
....:                initial_states=[0],
....:                final_states=[1])
sage: F([1])
(True, 1, ['a'])
sage: A([1])
True
sage: T([1])
['a']
sage: F([2])
(False, 2, ['b'])
sage: A([2])
False
sage: T([2])
Traceback (most recent call last):
...
ValueError: Invalid input sequence.
sage: F([3])
(False, None, None)
sage: A([3])
False
sage: T([3])
Traceback (most recent call last):
...
ValueError: Invalid input sequence.
sage: F = FiniteStateMachine([(11, 11, 1, 'a'), (11, 12, 2, 'b'),
....:                         (11, 13, 3, 'c'), (11, 14, 4, 'd'),
....:                         (12, 13, 3, 'e'), (12, 13, 3, 'f'),
....:                         (12, 14, 4, 'g'), (12, 14, 4, 'h'),
....:                         (12, 13, 2, 'i'), (12, 14, 2, 'j')],
....:                        initial_states=[11],
....:                        final_states=[13])
sage: def f(o):
....:     return ''.join(o)
sage: F([0], format_output=f)
(False, None, None)
sage: F([3], format_output=f)
(True, 13, 'c')
sage: F([4], format_output=f)
(False, 14, 'd')
sage: F([2, 2], format_output=f)
Traceback (most recent call last):
...
ValueError: Got more than one output, but only allowed to show
one. Change list_of_outputs option.
sage: F([2, 2], format_output=f, list_of_outputs=True)
[(True, 13, 'bi'), (False, 14, 'bj')]
sage: F([2, 3], format_output=f)
Traceback (most recent call last):
...
ValueError: Got more than one output, but only allowed to show
one. Change list_of_outputs option.
sage: F([2, 3], format_output=f, list_of_outputs=True)
[(True, 13, 'be'), (True, 13, 'bf')]
sage: F([2, 4], format_output=f)
Traceback (most recent call last):
...
ValueError: Got more than one output, but only allowed to show
one. Change list_of_outputs option.
sage: F([2, 4], format_output=f, list_of_outputs=True)
[(False, 14, 'bg'), (False, 14, 'bh')]
sage: A = Automaton([(11, 11, 1), (11, 12, 2),
....:                (11, 13, 3), (11, 14, 4),
....:                (12, 13, 3), (12, 14, 4),
....:                (12, 32, 3), (12, 42, 4),
....:                (12, 13, 2), (12, 14, 2)],
....:               initial_states=[11],
....:               final_states=[13, 32])
sage: def f(o):
....:     return ''.join(o)
sage: A([0], format_output=f)
False
sage: A([3], format_output=f)
True
sage: A([4], format_output=f)
False
sage: A([2, 2], format_output=f)
True
sage: A([2, 2], format_output=f, list_of_outputs=True)
[True, False]
sage: A([2, 3], format_output=f)
True
sage: A([2, 3], format_output=f, list_of_outputs=True)
[True, True]
sage: A([2, 4], format_output=f)
False
sage: A([2, 4], format_output=f, list_of_outputs=True)
[False, False]
sage: T = Transducer([(11, 11, 1, 'a'), (11, 12, 2, 'b'),
....:                 (11, 13, 3, 'c'), (11, 14, 4, 'd'),
....:                 (12, 13, 3, 'e'), (12, 13, 3, 'f'),
....:                 (12, 14, 4, 'g'), (12, 14, 4, 'h'),
....:                 (12, 13, 2, 'i'), (12, 14, 2, 'j')],
....:                initial_states=[11],
....:                final_states=[13])
sage: def f(o):
....:     return ''.join(o)
sage: T([0], format_output=f)
Traceback (most recent call last):
...
ValueError: Invalid input sequence.
sage: T([3], format_output=f)
'c'
sage: T([4], format_output=f)
Traceback (most recent call last):
...
ValueError: Invalid input sequence.
sage: T([2, 2], format_output=f)
'bi'
sage: T([2, 2], format_output=f, list_of_outputs=True)
['bi', None]
sage: T([2, 2], format_output=f,
....:   list_of_outputs=True, only_accepted=True)
['bi']
sage: T.process([2, 2], format_output=f, list_of_outputs=True)
[(True, 13, 'bi'), (False, 14, 'bj')]
sage: T([2, 3], format_output=f)
Traceback (most recent call last):
...
ValueError: Found more than one accepting path.
sage: T([2, 3], format_output=f, list_of_outputs=True)
['be', 'bf']
sage: T([2, 4], format_output=f)
Traceback (most recent call last):
...
ValueError: Invalid input sequence.
sage: T([2, 4], format_output=f, list_of_outputs=True)
[None, None]
Kleene_closure()

TESTS:

sage: FiniteStateMachine().Kleene_closure()
Traceback (most recent call last):
...
NotImplementedError
accessible_components()

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

TESTS:

Check whether input of length > 1 works:

sage: F = Automaton([(0, 1, [0, 1]), (0, 2, 0)],
....:               initial_states=[0])
sage: F.accessible_components()
Automaton with 3 states
add_from_transition_function(function, initial_states=None, explore_existing_states=True)

Constructs a finite state machine from a transition function.

INPUT:

  • function may return a tuple (new_state, output_word) or a list of such tuples.
  • initial_states – If no initial states are given, the already existing initial states of self are taken.
  • If explore_existing_states is True (default), then already existing states in self (e.g. already given final states) will also be processed if they are reachable from the initial states.

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().
sage: def transition(state, where):
....:     return (vector([0, 0]), 1)
sage: Transducer(transition, input_alphabet=[0], initial_states=[0])
Traceback (most recent call last):
...
TypeError: mutable vectors are unhashable
add_state(state)

Adds a state to the finite state machine and returns the new state. If the state already exists, that existing state is returned.

INPUT:

  • state is either an instance of FSMState or, otherwise, a label of a state.

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'
add_states(states)

Adds several states. See add_state for more information.

INPUT:

  • states – a list of states or iterator over states.

OUTPUT:

Nothing.

EXAMPLES:

sage: F = FiniteStateMachine()
sage: F.add_states(['A', 'B'])
sage: F.states()
['A', 'B']
add_transition(*args, **kwargs)

Adds a transition to the finite state machine and returns the new transition.

If the transition already exists, the return value of self.on_duplicate_transition is returned. See the documentation of FiniteStateMachine.

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 transition.

add_transitions_from_function(function, labels_as_input=True)

Adds one or more transitions if function(state, state) says that there are some.

INPUT:

  • function – a transition function. Given two states from_state and to_state (or their labels if label_as_input is true), this function shall return a tuple (word_in, word_out) to add a transition from from_state to to_state with input and output labels word_in and word_out, respectively. If no such addition is to be added, the transition function shall return None. The transition function may also return a list of such tuples in order to add multiple transitions between the pair of states.
  • label_as_input – (default: True)

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

Multiple transitions are also possible:

sage: F = FiniteStateMachine()
sage: F.add_states([0, 1])
sage: def f(state1, state2):
....:     if state1 != state2:
....:          return [(0, 1), (1, 0)]
....:     else:
....:          return None
sage: F.add_transitions_from_function(f)
sage: F.transitions()
[Transition from 0 to 1: 0|1,
 Transition from 0 to 1: 1|0,
 Transition from 1 to 0: 0|1,
 Transition from 1 to 0: 1|0]

TESTS:

sage: F = FiniteStateMachine()
sage: F.add_state(0)
0
sage: def f(state1, state2):
....:     return 1
sage: F.add_transitions_from_function(f)
Traceback (most recent call last):
...
ValueError: The callback function for add_transitions_from_function
is expected to return a pair (word_in, word_out) or a list of such
pairs. For states 0 and 0 however, it returned 1,
which is not acceptable.
adjacency_matrix(input=None, entry=None)

Returns the adjacency matrix of the underlying graph.

INPUT:

  • input – Only transitions with input label input are respected.
  • entry – The function entry takes a transition and the return value is written in the matrix as the entry (transition.from_state, transition.to_state). The default value (None) of entry takes the variable x to the power of the sum of the output word of the transition.

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.

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]

This is equivalent to:

sage: matrix(B)
[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]

It is also possible to use other entries in the adjacency matrix:

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)]
sage: a = Automaton([(0, 1, 0),
....:                (1, 2, 0),
....:                (2, 0, 1),
....:                (2, 1, 0)],
....:               initial_states=[0],
....:               final_states=[0])
sage: a.adjacency_matrix()
[0 1 0]
[0 0 1]
[1 1 0]
asymptotic_moments(variable=n)

Returns the main terms of expectation and variance of the sum of output labels and its covariance with the sum of input labels.

INPUT:

  • variable – a symbol denoting the length of the input, by default \(n\).

OUTPUT:

A dictionary consisting of

  • expectation\(e n + \operatorname{Order}(1)\),
  • variance\(v n + \operatorname{Order}(1)\),
  • covariance\(c n + \operatorname{Order}(1)\)

for suitable constants \(e\), \(v\) and \(c\).

Assume that all input and output labels are numbers and that self is complete and has only one final component. Assume further that this final component is aperiodic. Furthermore, assume that there is exactly one initial state and that all states are final.

Denote by \(X_n\) the sum of output labels written by the finite state machine when reading a random input word of length \(n\) over the input alphabet (assuming equidistribution).

Then the expectation of \(X_n\) is \(en+O(1)\), the variance of \(X_n\) is \(vn+O(1)\) and the covariance of \(X_n\) and the sum of input labels is \(cn+O(1)\), cf. [HKW2014], Theorem 3.9.

In the case of non-integer input or output labels, performance degrades significantly. For rational input and output labels, consider rescaling to integers. This limitation comes from the fact that determinants over polynomial rings can be computed much more efficiently than over the symbolic ring. In fact, we compute (parts) of a trivariate generating function where the input and output labels are exponents of some indeterminates, see [HKW2014], Theorem 3.9 for details. If those exponents are integers, we can use a polynomial ring.

EXAMPLES:

  1. A trivial example: write the negative of the input:

    sage: T = Transducer([(0, 0, 0, 0), (0, 0, 1, -1)],
    ....:                initial_states=[0],
    ....:                final_states=[0])
    sage: T([0, 1, 1])
    [0, -1, -1]
    sage: moments = T.asymptotic_moments()
    sage: moments['expectation']
    -1/2*n + Order(1)
    sage: moments['variance']
    1/4*n + Order(1)
    sage: moments['covariance']
    -1/4*n + Order(1)
    
  2. For the case of the Hamming weight of the non-adjacent-form (NAF) of integers, cf. the Wikipedia article Non-adjacent_form and the example on recognizing NAFs, the following agrees with the results in [HP2007].

    We first use the transducer to convert the standard binary expansion to the NAF given in [HP2007]. We use the parameter with_final_word_out such that we do not have to add sufficiently many trailing zeros:

    sage: NAF = Transducer([(0, 0, 0, 0),
    ....:                   (0, '.1', 1, None),
    ....:                   ('.1', 0, 0, [1, 0]),
    ....:                   ('.1', 1, 1, [-1, 0]),
    ....:                   (1, 1, 1, 0),
    ....:                   (1, '.1', 0, None)],
    ....:                  initial_states=[0],
    ....:                  final_states=[0],
    ....:                  with_final_word_out=[0])
    

    As an example, we compute the NAF of \(27\) by this transducer.

    sage: binary_27 = 27.bits()
    sage: binary_27
    [1, 1, 0, 1, 1]
    sage: NAF_27 = NAF(binary_27)
    sage: NAF_27
    [-1, 0, -1, 0, 0, 1, 0]
    sage: ZZ(NAF_27, base=2)
    27
    

    Next, we are only interested in the Hamming weight:

    sage: def weight(state, input):
    ....:     if input is None:
    ....:         result = 0
    ....:     else:
    ....:         result = ZZ(input != 0)
    ....:     return (0, result)
    sage: weight_transducer = Transducer(weight,
    ....:                                input_alphabet=[-1, 0, 1],
    ....:                                initial_states=[0],
    ....:                                final_states=[0])
    

    At the moment, we can not use composition with NAF, because it has non-empty final output words:

    sage: NAFweight = weight_transducer.composition(
    ....:     NAF,
    ....:     algorithm='explorative')
    Traceback (most recent call last):
    ...
    NotImplementedError: Explorative composition is not
    implemented for transducers with non-empty final output
    words. Try the direct algorithm instead.
    

    Thus, we change NAF, then compose and again construct the final output words:

    sage: for s in NAF.final_states():
    ....:     s.final_word_out = []
    sage: NAFweight = weight_transducer.composition(
    ....:     NAF,
    ....:     algorithm='explorative').relabeled()
    sage: NAFweight.construct_final_word_out(0)
    sage: sorted(NAFweight.transitions())
    [Transition from 0 to 0: 0|0,
     Transition from 0 to 1: 1|-,
     Transition from 1 to 0: 0|1,0,
     Transition from 1 to 2: 1|1,0,
     Transition from 2 to 1: 0|-,
     Transition from 2 to 2: 1|0]
    sage: NAFweight(binary_27 + [0, 0])
    [1, 0, 1, 0, 0, 1, 0]
    

    Now, we actually compute the asymptotic moments:

    sage: moments = NAFweight.asymptotic_moments()
    sage: moments['expectation']
    1/3*n + Order(1)
    sage: moments['variance']
    2/27*n + Order(1)
    sage: moments['covariance']
    Order(1)
    
  3. This is Example 3.16 in [HKW2014], where a transducer with variable output labels is given. There, the aim was to choose the output labels of this very simple transducer such that the input and output sum are asymptotically independent, i.e., the constant \(c\) vanishes.

    sage: var('a_1, a_2, a_3, a_4')
    (a_1, a_2, a_3, a_4)
    sage: T = Transducer([[0, 0, 0, a_1], [0, 1, 1, a_3],
    ....:                 [1, 0, 0, a_4], [1, 1, 1, a_2]],
    ....:                initial_states=[0], final_states=[0, 1])
    sage: moments = T.asymptotic_moments()
    verbose 0 (...) Non-integer output weights lead to
    significant performance degradation.
    sage: moments['expectation']
    1/4*(a_1 + a_2 + a_3 + a_4)*n + Order(1)
    sage: moments['covariance']
    -1/4*(a_1 - a_2)*n + Order(1)
    

    Therefore, the asymptotic covariance vanishes if and only if \(a_2=a_1\).

  4. This is Example 4.3 in [HKW2014], dealing with the transducer converting the binary expansion of an integer into Gray code (cf. the Wikipedia article Gray_code and the example on Gray code):

    sage: moments = transducers.GrayCode().asymptotic_moments()
    sage: moments['expectation']
    1/2*n + Order(1)
    sage: moments['variance']
    1/4*n + Order(1)
    sage: moments['covariance']
    Order(1)
    
  5. This is the first part of Example 4.4 in [HKW2014], counting the number of 10 blocks in the standard binary expansion. The least significant digit is at the left-most position:

    sage: block10 = transducers.CountSubblockOccurrences(
    ....:     [1, 0],
    ....:     input_alphabet=[0, 1])
    sage: sorted(block10.transitions())
    [Transition from () to (): 0|0,
     Transition from () to (1,): 1|0,
     Transition from (1,) to (): 0|1,
     Transition from (1,) to (1,): 1|0]
    sage: moments = block10.asymptotic_moments()
    sage: moments['expectation']
    1/4*n + Order(1)
    sage: moments['variance']
    1/16*n + Order(1)
    sage: moments['covariance']
    Order(1)
    
  6. This is the second part of Example 4.4 in [HKW2014], counting the number of 11 blocks in the standard binary expansion. The least significant digit is at the left-most position:

    sage: block11 = transducers.CountSubblockOccurrences(
    ....:     [1, 1],
    ....:     input_alphabet=[0, 1])
    sage: sorted(block11.transitions())
    [Transition from () to (): 0|0,
     Transition from () to (1,): 1|0,
     Transition from (1,) to (): 0|0,
     Transition from (1,) to (1,): 1|1]
    sage: var('N')
    N
    sage: moments = block11.asymptotic_moments(N)
    sage: moments['expectation']
    1/4*N + Order(1)
    sage: moments['variance']
    5/16*N + Order(1)
    sage: correlation = (moments['covariance'].coefficient(N) /
    ....:                (1/2 * sqrt(moments['variance'].coefficient(N))))
    sage: correlation
    2/5*sqrt(5)
    
  7. This is Example 4.5 in [HKW2014], counting the number of 01 blocks minus the number of 10 blocks in the standard binary expansion. The least significant digit is at the left-most position:

    sage: block01 = transducers.CountSubblockOccurrences(
    ....:     [0, 1],
    ....:     input_alphabet=[0, 1])
    sage: sage.combinat.finite_state_machine.FSMOldCodeTransducerCartesianProduct = False
    sage: product_01x10 = block01.cartesian_product(block10)
    sage: block_difference = transducers.sub([0, 1])(product_01x10)
    sage: T = block_difference.simplification().relabeled()
    sage: sage.combinat.finite_state_machine.FSMOldCodeTransducerCartesianProduct = True
    sage: T.transitions()
    [Transition from 0 to 1: 0|-1,
     Transition from 0 to 0: 1|0,
     Transition from 1 to 1: 0|0,
     Transition from 1 to 0: 1|1,
     Transition from 2 to 1: 0|0,
     Transition from 2 to 0: 1|0]
    sage: moments = T.asymptotic_moments()
    sage: moments['expectation']
    Order(1)
    sage: moments['variance']
    Order(1)
    sage: moments['covariance']
    Order(1)
    
  8. The finite state machine must have a unique final component:

    sage: T = Transducer([(0, -1, -1, -1), (0, 1, 1, 1),
    ....:                 (-1, -1, -1, -1), (-1, -1, 1, -1),
    ....:                 (1, 1, -1, 1), (1, 1, 1, 1)],
    ....:                initial_states=[0],
    ....:                final_states=[0, 1, -1])
    sage: T.asymptotic_moments()
    Traceback (most recent call last):
    ...
    NotImplementedError: asymptotic_moments is only
    implemented for finite state machines with one final
    component.
    

    In this particular example, the first letter of the input decides whether we reach the loop at \(-1\) or the loop at \(1\). In the first case, we have \(X_n = -n\), while we have \(X_n = n\) in the second case. Therefore, the expectation \(E(X_n)\) of \(X_n\) is \(E(X_n) = 0\). We get \((X_n-E(X_n))^2 = n^2\) in all cases, which results in a variance of \(n^2\).

    So this example shows that the variance may be non-linear if there is more than one final component.

TESTS:

  1. An input alphabet must be given:

    sage: T = Transducer([[0, 0, 0, 0]],
    ....:                initial_states=[0], final_states=[0],
    ....:                determine_alphabets=False)
    sage: T.asymptotic_moments()
    Traceback (most recent call last):
    ...
    ValueError: No input alphabet is given.
    Try calling determine_alphabets().
    
  2. The finite state machine must have a unique initial state:

    sage: T = Transducer([(0, 0, 0, 0)])
    sage: T.asymptotic_moments()
    Traceback (most recent call last):
    ...
    ValueError: A unique initial state is required.
    
  3. The finite state machine must be complete:

    sage: T = Transducer([[0, 0, 0, 0]],
    ....:                initial_states=[0], final_states=[0],
    ....:                input_alphabet=[0, 1])
    sage: T.asymptotic_moments()
    Traceback (most recent call last):
    ...
    NotImplementedError: This finite state machine is
    not complete.
    
  4. The final component of the finite state machine must be aperiodic:

    sage: T = Transducer([(0, 1, 0, 0), (1, 0, 0, 0)],
    ....:                initial_states=[0], final_states=[0, 1])
    sage: T.asymptotic_moments()
    Traceback (most recent call last):
    ...
    NotImplementedError: asymptotic_moments is only
    implemented for finite state machines whose unique final
    component is aperiodic.
    
  5. Non-integer input or output labels lead to a warning:

    sage: T = Transducer([[0, 0, 0, 0], [0, 0, 1, -1/2]],
    ....:                initial_states=[0], final_states=[0])
    sage: moments = T.asymptotic_moments()
    verbose 0 (...) Non-integer output weights lead to
    significant performance degradation.
    sage: moments['expectation']
    -1/4*n + Order(1)
    sage: moments['variance']
    1/16*n + Order(1)
    sage: moments['covariance']
    -1/8*n + Order(1)
    

    This warning can be silenced by set_verbose():

    sage: set_verbose(-1, "finite_state_machine.py")
    sage: moments = T.asymptotic_moments()
    sage: moments['expectation']
    -1/4*n + Order(1)
    sage: moments['variance']
    1/16*n + Order(1)
    sage: moments['covariance']
    -1/8*n + Order(1)
    sage: set_verbose(0, "finite_state_machine.py")
    
  6. Check whether word_out of FSMState are correctly dealt with:

    sage: from sage.combinat.finite_state_machine import FSMState
    sage: s = FSMState(0, word_out=2,
    ....:              is_initial=True,
    ....:              is_final=True)
    sage: T = Transducer([(s, s, 0, 1)],
    ....:                initial_states=[s], final_states=[s])
    sage: T([0, 0])
    [2, 1, 2, 1, 2]
    sage: T.asymptotic_moments()['expectation']
    3*n + Order(1)
    

    The same test for non-integer output:

    sage: from sage.combinat.finite_state_machine import FSMState
    sage: s = FSMState(0, word_out=2/3)
    sage: T = Transducer([(s, s, 0, 1/2)],
    ....:                initial_states=[s], final_states=[s])
    sage: T.asymptotic_moments()['expectation']
    verbose 0 (...) Non-integer output weights lead to
    significant performance degradation.
    7/6*n + Order(1)
    
  7. All states of self have to be final:

    sage: T = Transducer([(0, 1, 1, 4)], initial_states=[0])
    sage: T.asymptotic_moments()
    Traceback (most recent call last):
    ...
    ValueError: Not all states are final.
    

ALGORITHM:

See [HKW2014], Theorem 3.9.

REFERENCES:

[HKW2014](1, 2, 3, 4, 5, 6, 7, 8, 9) Clemens Heuberger, Sara Kropf and Stephan Wagner, Variances and Covariances in the Central Limit Theorem for the Output of a Transducer, Arxiv 1404.3680v2.
[HP2007](1, 2) Clemens Heuberger and Helmut Prodinger, The Hamming Weight of the Non-Adjacent-Form under Various Input Statistics, Periodica Mathematica Hungarica Vol. 55 (1), 2007, pp. 81–96, doi:10.1007/s10998-007-3081-z.
composition(other, algorithm=None, only_accessible_components=True)

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. The color of a new state is the tuple of colors of the constituent states.

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]

Also final output words are considered if algorithm='direct' or None:

sage: F = Transducer([('A', 'B', 1, 0), ('B', 'A', 0, 1)],
....:                initial_states=['A', 'B'],
....:                final_states=['A', 'B'])
sage: F.state('A').final_word_out = 0
sage: F.state('B').final_word_out = 1
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])
sage: G.state(2).final_word_out = 0
sage: Hd = F.composition(G, algorithm='direct')
sage: Hd.final_states()
[(2, 'B')]

Note that (2, 'A') is not final, as the final output \(0\) of state \(2\) of \(G\) cannot be processed in state 'A' of \(F\).

sage: [s.final_word_out for s in Hd.final_states()]
[[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

In the explorative algorithm, transducers with non-empty final output words are currently not implemented:

sage: A = transducers.GrayCode()
sage: B = transducers.abs([0, 1])
sage: A.composition(B, algorithm='explorative')
Traceback (most recent call last):
...
NotImplementedError: Explorative composition is not
implemented for transducers with non-empty final output
words. Try the direct algorithm instead.

Similarly, the explorative algorithm cannot handle non-deterministic finite state machines:

sage: A = Transducer([(0, 0, 0, 0), (0, 1, 0, 0)])
sage: B = transducers.Identity([0])
sage: A.composition(B, algorithm='explorative')
Traceback (most recent call last):
...
NotImplementedError: Explorative composition is currently
not implemented for non-deterministic transducers.
sage: B.composition(A, algorithm='explorative')
Traceback (most recent call last):
...
NotImplementedError: Explorative composition is currently
not implemented for non-deterministic transducers.

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')

In the following examples, we compose transducers and automata and check whether the types are correct.

sage: from sage.combinat.finite_state_machine import (
....:     is_Automaton, is_Transducer)
sage: T = Transducer([(0, 0, 0, 0)], initial_states=[0])
sage: A = Automaton([(0, 0, 0)], initial_states=[0])
sage: is_Transducer(T.composition(T, algorithm='direct'))
True
sage: is_Transducer(T.composition(T, algorithm='explorative'))
True
sage: T.composition(A, algorithm='direct')
Traceback (most recent call last):
...
TypeError: Composition with automaton is not possible.
sage: T.composition(A, algorithm='explorative')
Traceback (most recent call last):
...
TypeError: Composition with automaton is not possible.
sage: A.composition(A, algorithm='direct')
Traceback (most recent call last):
...
TypeError: Composition with automaton is not possible.
sage: A.composition(A, algorithm='explorative')
Traceback (most recent call last):
...
TypeError: Composition with automaton is not possible.
sage: is_Automaton(A.composition(T, algorithm='direct'))
True
sage: is_Automaton(A.composition(T, algorithm='explorative'))
True
concatenation(other)

TESTS:

sage: F = FiniteStateMachine([('A', 'A')])
sage: FiniteStateMachine().concatenation(F)
Traceback (most recent call last):
...
NotImplementedError
construct_final_word_out(letters, allow_non_final=True)

This is an inplace version of with_final_word_out(). See with_final_word_out() for documentation and examples.

TESTS:

sage: T = Transducer([(0, 1, 0, 0), (1, 0, 0, 1)],
....:                initial_states=[0],
....:                final_states=[0])
sage: F = T.with_final_word_out(0)
sage: T.construct_final_word_out(0)
sage: T == F  # indirect doctest
True
sage: T = Transducer([(0, 1, 0, None)],
....:                final_states=[1])
sage: F = T.with_final_word_out(0)
sage: F.state(0).final_word_out
[]
copy()

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
deepcopy(memo=None)

Returns a deep copy of the finite state machine.

INPUT:

  • memo – (default: None) a dictionary storing already processed elements.

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

TESTS:

Make sure that the links between transitions and states are still intact:

sage: C = deepcopy(F)
sage: C.transitions()[0].from_state is C.state('A')
True
sage: C.transitions()[0].to_state is C.state('A')
True
default_format_letter(x, combine_all=False)

Return a LatexExpr built out of the argument x.

INPUT:

  • x – a Sage object
  • combine_all – boolean (Default: False) If combine_all is True and the input is a tuple, then it does not return a tuple and instead returns a string with all the elements separated by a single space.

OUTPUT:

A LatexExpr built from x

EXAMPLES:

sage: latex(Integer(3))  # indirect doctest
3
sage: latex(1==0)
\mathrm{False}
sage: print latex([x,2])
\left[x, 2\right]

Check that trac ticket #11775 is fixed:

sage: latex((x,2), combine_all=True)
x 2
default_format_transition_label(word)

Default formatting of words in transition labels for LaTeX output.

INPUT:

word – list of letters

OUTPUT:

String representation of word suitable to be typeset in mathematical mode.

  • For a non-empty word: Concatenation of the letters, piped through self.format_letter and separated by blanks.
  • For an empty word: sage.combinat.finite_state_machine.EmptyWordLaTeX.

There is also a variant format_transition_label_reversed() writing the words in reversed order.

EXAMPLES:

  1. Example of a non-empty word:

    sage: T = Transducer()
    sage: print T.default_format_transition_label(
    ....:    ['a', 'alpha', 'a_1', '0', 0, (0, 1)])
    \text{\texttt{a}} \text{\texttt{alpha}}
    \text{\texttt{a{\char`\_}1}} 0 0 \left(0, 1\right)
    
  2. In the example above, 'a' and 'alpha' should perhaps be symbols:

    sage: var('a alpha a_1')
    (a, alpha, a_1)
    sage: print T.default_format_transition_label([a, alpha, a_1])
    a \alpha a_{1}
    
  3. Example of an empty word:

    sage: print T.default_format_transition_label([])
    \varepsilon
    

    We can change this by setting sage.combinat.finite_state_machine.EmptyWordLaTeX:

    sage: sage.combinat.finite_state_machine.EmptyWordLaTeX = ''
    sage: T.default_format_transition_label([])
    ''
    

    Finally, we restore the default value:

    sage: sage.combinat.finite_state_machine.EmptyWordLaTeX = r'\varepsilon'
    
  4. This method is the default value for FiniteStateMachine.format_transition_label. That can be changed to be any other function:

    sage: A = Automaton([(0, 1, 0)])
    sage: def custom_format_transition_label(word):
    ....:     return "t"
    sage: A.latex_options(format_transition_label=custom_format_transition_label)
    sage: print latex(A)
    \begin{tikzpicture}[auto, initial text=, >=latex]
    \node[state] (v0) at (3.000000, 0.000000) {$0$};
    \node[state] (v1) at (-3.000000, 0.000000) {$1$};
    \path[->] (v0) edge node[rotate=360.00, anchor=south] {$t$} (v1);
    \end{tikzpicture}
    

TEST:

Check that #16357 is fixed:

sage: T = Transducer()
sage: T.default_format_transition_label([])
'\\varepsilon'
sage: T.default_format_transition_label(iter([]))
'\\varepsilon'
delete_state(s)

Deletes a state and all transitions coming or going to this state.

INPUT:

  • s – a label of a state or an FSMState.

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|-]

TESTS:

sage: F._states_
['B']
sage: F._states_dict_  # This shows that #16024 is fixed.
{'B': 'B'}
delete_transition(t)

Deletes a transition by removing it from the list of transitions of the state, where the transition starts.

INPUT:

  • t – a transition.

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|-]
determine_alphabets(reset=True)

Determines the input and output alphabet according to the transitions in self.

INPUT:

  • reset – If reset is True, then the existing input and output alphabets are erased, otherwise new letters are appended to the existing alphabets.

OUTPUT:

Nothing.

After this operation the input alphabet and the output alphabet of self are a list of letters.

Todo

At the moment, the letters of the alphabets need to be hashable.

EXAMPLES:

sage: T = Transducer([(1, 1, 1, 0), (1, 2, 2, 1),
....:                 (2, 2, 1, 1), (2, 2, 0, 0)],
....:                final_states=[1],
....:                determine_alphabets=False)
sage: T.state(1).final_word_out = [1, 4]
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, 4])
digraph(edge_labels='words_in_out')

Returns the graph of the finite state machine with labeled vertices and labeled edges.

INPUT:

  • edge_label: (default: 'words_in_out') can be
    • 'words_in_out' (labels will be strings 'i|o')
    • a function with which takes as input a transition and outputs (returns) the label

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
disjoint_union(other)

TESTS:

sage: F = FiniteStateMachine([('A', 'A')])
sage: FiniteStateMachine().disjoint_union(F)
Traceback (most recent call last):
...
NotImplementedError
empty_copy(memo=None, new_class=None)

Returns an empty deep copy of the finite state machine, i.e., input_alphabet, output_alphabet, on_duplicate_transition are preserved, but states and transitions are not.

INPUT:

  • memo – a dictionary storing already processed elements.
  • new_class – a class for the copy. By default (None), the class of self is used.

OUTPUT:

A new finite state machine.

EXAMPLES:

sage: from sage.combinat.finite_state_machine import duplicate_transition_raise_error
sage: F = FiniteStateMachine([('A', 'A', 0, 2), ('A', 'A', 1, 3)],
....:                        input_alphabet=[0, 1],
....:                        output_alphabet=[2, 3],
....:                        on_duplicate_transition=duplicate_transition_raise_error)
sage: FE = F.empty_copy(); FE
Finite state machine with 0 states
sage: FE.input_alphabet
[0, 1]
sage: FE.output_alphabet
[2, 3]
sage: FE.on_duplicate_transition == duplicate_transition_raise_error
True

TESTS:

sage: T = Transducer()
sage: type(T.empty_copy())
<class 'sage.combinat.finite_state_machine.Transducer'>
sage: type(T.empty_copy(new_class=Automaton))
<class 'sage.combinat.finite_state_machine.Automaton'>
epsilon_successors(state)

Returns the dictionary with states reachable from state without reading anything from an input tape as keys. The values are lists of outputs.

INPUT:

  • state – the state whose epsilon successors should be determined.

OUTPUT:

A dictionary mapping states to a list of output words.

The states in the output are the epsilon successors of state. Each word of the list of output words is a word written when taking a path from state to the corresponding state.

EXAMPLES:

sage: T = Transducer([(0, 1, None, 'a'), (1, 2, None, 'b')])
sage: T.epsilon_successors(0)
{1: [['a']], 2: [['a', 'b']]}
sage: T.epsilon_successors(1)
{2: [['b']]}
sage: T.epsilon_successors(2)
{}

If there is a cycle with only epsilon transitions, then this cycle is only processed once and there is no infinite loop:

sage: S = Transducer([(0, 1, None, 'a'), (1, 0, None, 'b')])
sage: S.epsilon_successors(0)
{0: [['a', 'b']], 1: [['a']]}
sage: S.epsilon_successors(1)
{0: [['b']], 1: [['b', 'a']]}
equivalence_classes()

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 there is a bijection \(\varphi\) between paths starting at \(a\) and paths starting at \(b\) with the following properties: Let \(p_a\) be a path from \(a\) to \(a'\) and \(p_b\) a path from \(b\) to \(b'\) such that \(\varphi(p_a)=p_b\), then

  • \(p_a.\mathit{word}_\mathit{in}=p_b.\mathit{word}_\mathit{in}\),
  • \(p_a.\mathit{word}_\mathit{out}=p_b.\mathit{word}_\mathit{out}\),
  • \(a'\) and \(b'\) have the same output label, and
  • \(a'\) and \(b'\) are both final or both non-final and have the same final output word.

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

minimization()

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: sorted(fsm.equivalence_classes())
[['A', 'C'], ['B', 'D']]
sage: fsm.state("A").is_final = True
sage: sorted(fsm.equivalence_classes())
[['A'], ['B'], ['C'], ['D']]
sage: fsm.state("C").is_final = True
sage: sorted(fsm.equivalence_classes())
[['A', 'C'], ['B', 'D']]
sage: fsm.state("A").final_word_out = 1
sage: sorted(fsm.equivalence_classes())
[['A'], ['B'], ['C'], ['D']]
sage: fsm.state("C").final_word_out = 1
sage: sorted(fsm.equivalence_classes())
[['A', 'C'], ['B', 'D']]
final_components()

Returns the final components of a finite state machine as finite state machines.

INPUT:

Nothing.

OUTPUT:

A list of finite state machines, each representing a final component of self.

A final component of a transducer T is a strongly connected component C such that there are no transitions of T leaving C.

The final components are the only parts of a transducer which influence the main terms of the asympotic behaviour of the sum of output labels of a transducer, see [HKP2014] and [HKW2014].

EXAMPLES:

sage: T = Transducer([['A', 'B', 0, 0], ['B', 'C', 0, 1],
....:                 ['C', 'B', 0, 1], ['A', 'D', 1, 0],
....:                 ['D', 'D', 0, 0], ['D', 'B', 1, 0],
....:                 ['A', 'E', 2, 0], ['E', 'E', 0, 0]])
sage: FC = T.final_components()
sage: sorted(FC[0].transitions())
[Transition from 'B' to 'C': 0|1,
 Transition from 'C' to 'B': 0|1]
sage: FC[1].transitions()
[Transition from 'E' to 'E': 0|0]

Another example (cycle of length 2):

sage: T = Automaton([[0, 1, 0], [1, 0, 0]])
sage: len(T.final_components()) == 1
True
sage: T.final_components()[0].transitions()
[Transition from 0 to 1: 0|-,
 Transition from 1 to 0: 0|-]

REFERENCES:

[HKP2014]Clemens Heuberger, Sara Kropf, and Helmut Prodinger, Asymptotic analysis of the sum of the output of transducer, in preparation.
final_states()

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']
format_letter(x, combine_all=False)

Return a LatexExpr built out of the argument x.

INPUT:

  • x – a Sage object
  • combine_all – boolean (Default: False) If combine_all is True and the input is a tuple, then it does not return a tuple and instead returns a string with all the elements separated by a single space.

OUTPUT:

A LatexExpr built from x

EXAMPLES:

sage: latex(Integer(3))  # indirect doctest
3
sage: latex(1==0)
\mathrm{False}
sage: print latex([x,2])
\left[x, 2\right]

Check that trac ticket #11775 is fixed:

sage: latex((x,2), combine_all=True)
x 2
format_letter_negative(letter)

Format negative numbers as overlined numbers, everything else by standard LaTeX formatting.

INPUT:

letter – anything.

OUTPUT:

Overlined absolute value if letter is a negative integer, latex(letter) otherwise.

EXAMPLES:

sage: A = Automaton([(0, 0, -1)])
sage: map(A.format_letter_negative, [-1, 0, 1, 'a', None])
 ['\\overline{1}', 0, 1, \text{\texttt{a}}, \mbox{\rm None}]
sage: A.latex_options(format_letter=A.format_letter_negative)
sage: print(latex(A))
\begin{tikzpicture}[auto, initial text=, >=latex]
\node[state] (v0) at (3.000000, 0.000000) {$0$};
\path[->] (v0) edge[loop above] node {$\overline{1}$} ();
\end{tikzpicture}
format_transition_label(word)

Default formatting of words in transition labels for LaTeX output.

INPUT:

word – list of letters

OUTPUT:

String representation of word suitable to be typeset in mathematical mode.

  • For a non-empty word: Concatenation of the letters, piped through self.format_letter and separated by blanks.
  • For an empty word: sage.combinat.finite_state_machine.EmptyWordLaTeX.

There is also a variant format_transition_label_reversed() writing the words in reversed order.

EXAMPLES:

  1. Example of a non-empty word:

    sage: T = Transducer()
    sage: print T.default_format_transition_label(
    ....:    ['a', 'alpha', 'a_1', '0', 0, (0, 1)])
    \text{\texttt{a}} \text{\texttt{alpha}}
    \text{\texttt{a{\char`\_}1}} 0 0 \left(0, 1\right)
    
  2. In the example above, 'a' and 'alpha' should perhaps be symbols:

    sage: var('a alpha a_1')
    (a, alpha, a_1)
    sage: print T.default_format_transition_label([a, alpha, a_1])
    a \alpha a_{1}
    
  3. Example of an empty word:

    sage: print T.default_format_transition_label([])
    \varepsilon
    

    We can change this by setting sage.combinat.finite_state_machine.EmptyWordLaTeX:

    sage: sage.combinat.finite_state_machine.EmptyWordLaTeX = ''
    sage: T.default_format_transition_label([])
    ''
    

    Finally, we restore the default value:

    sage: sage.combinat.finite_state_machine.EmptyWordLaTeX = r'\varepsilon'
    
  4. This method is the default value for FiniteStateMachine.format_transition_label. That can be changed to be any other function:

    sage: A = Automaton([(0, 1, 0)])
    sage: def custom_format_transition_label(word):
    ....:     return "t"
    sage: A.latex_options(format_transition_label=custom_format_transition_label)
    sage: print latex(A)
    \begin{tikzpicture}[auto, initial text=, >=latex]
    \node[state] (v0) at (3.000000, 0.000000) {$0$};
    \node[state] (v1) at (-3.000000, 0.000000) {$1$};
    \path[->] (v0) edge node[rotate=360.00, anchor=south] {$t$} (v1);
    \end{tikzpicture}
    

TEST:

Check that #16357 is fixed:

sage: T = Transducer()
sage: T.default_format_transition_label([])
'\\varepsilon'
sage: T.default_format_transition_label(iter([]))
'\\varepsilon'
format_transition_label_reversed(word)

Format words in transition labels in reversed order.

INPUT:

word – list of letters.

OUTPUT:

String representation of word suitable to be typeset in mathematical mode, letters are written in reversed order.

This is the reversed version of default_format_transition_label().

In digit expansions, digits are frequently processed from the least significant to the most significant position, but it is customary to write the least significant digit at the right-most position. Therefore, the labels have to be reversed.

EXAMPLE:

sage: T = Transducer([(0, 0, 0, [1, 2, 3])])
sage: T.format_transition_label_reversed([1, 2, 3])
'3 2 1'
sage: T.latex_options(format_transition_label=T.format_transition_label_reversed)
sage: print latex(T)
\begin{tikzpicture}[auto, initial text=, >=latex]
\node[state] (v0) at (3.000000, 0.000000) {$0$};
\path[->] (v0) edge[loop above] node {$0\mid 3 2 1$} ();
\end{tikzpicture}

TEST:

Check that #16357 is fixed:

sage: T = Transducer()
sage: T.format_transition_label_reversed([])
'\\varepsilon'
graph(edge_labels='words_in_out')

Returns the graph of the finite state machine with labeled vertices and labeled edges.

INPUT:

  • edge_label: (default: 'words_in_out') can be
    • 'words_in_out' (labels will be strings 'i|o')
    • a function with which takes as input a transition and outputs (returns) the label

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
has_final_state(state)

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
has_final_states()

Returns whether the finite state machine has a final state.

INPUT:

Nothing.

OUTPUT:

True or False.

EXAMPLES:

sage: FiniteStateMachine().has_final_states()
False
has_initial_state(state)

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
has_initial_states()

Returns whether the finite state machine has an initial state.

INPUT:

Nothing.

OUTPUT:

True or False.

EXAMPLES:

sage: FiniteStateMachine().has_initial_states()
False
has_state(state)

Returns whether state is one of the states of the finite state machine.

INPUT:

  • state can be a FSMState or a label of a state.

OUTPUT:

True or False.

EXAMPLES:

sage: FiniteStateMachine().has_state('A')
False
has_transition(transition)

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.
induced_sub_finite_state_machine(states)

Returns a sub-finite-state-machine of the finite state machine induced by the given states.

INPUT:

  • states – a list (or an iterator) of states (either labels or instances of FSMState) of the sub-finite-state-machine.

OUTPUT:

A new finite state machine. It consists (of deep copies) of the given states and (deep copies) of all transitions of self between these states.

EXAMPLE:

sage: FSM = FiniteStateMachine([(0, 1, 0), (0, 2, 0),
....:                           (1, 2, 0), (2, 0, 0)])
sage: sub_FSM = FSM.induced_sub_finite_state_machine([0, 1])
sage: sub_FSM.states()
[0, 1]
sage: sub_FSM.transitions()
[Transition from 0 to 1: 0|-]
sage: FSM.induced_sub_finite_state_machine([3])
Traceback (most recent call last):
...
ValueError: 3 is not a state of this finite state machine.

TESTS:

Make sure that the links between transitions and states are still intact:

sage: sub_FSM.transitions()[0].from_state is sub_FSM.state(0)
True
initial_states()

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']
input_projection()

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|-]
intersection(other)

TESTS:

sage: FiniteStateMachine().intersection(FiniteStateMachine())
Traceback (most recent call last):
...
NotImplementedError
is_Markov_chain(is_zero=None)

Checks whether self is a Markov chain where the transition probabilities are modeled as input labels.

INPUT:

  • is_zero – by default (is_zero=None), checking for zero is simply done by is_zero(). This parameter can be used to provide a more sophisticated check for zero, e.g. in the case of symbolic probabilities, see the examples below.

OUTPUT:

True or False.

on_duplicate_transition must be duplicate_transition_add_input() and the sum of the input weights of the transitions leaving a state must add up to 1.

EXAMPLES:

sage: from sage.combinat.finite_state_machine import duplicate_transition_add_input
sage: F = Transducer([[0, 0, 1/4, 0], [0, 1, 3/4, 1],
....:                 [1, 0, 1/2, 0], [1, 1, 1/2, 1]],
....:                on_duplicate_transition=duplicate_transition_add_input)
sage: F.is_Markov_chain()
True

on_duplicate_transition must be duplicate_transition_add_input():

sage: F = Transducer([[0, 0, 1/4, 0], [0, 1, 3/4, 1],
....:                 [1, 0, 1/2, 0], [1, 1, 1/2, 1]])
sage: F.is_Markov_chain()
False

Sum of input labels of the transitions leaving states must be 1:

sage: F = Transducer([[0, 0, 1/4, 0], [0, 1, 3/4, 1],
....:                 [1, 0, 1/2, 0]],
....:                on_duplicate_transition=duplicate_transition_add_input)
sage: F.is_Markov_chain()
False

If the probabilities are variables in the symbolic ring, assume() will do the trick:

sage: var('p q')
(p, q)
sage: F = Transducer([(0, 0, p, 1), (0, 0, q, 0)],
....:                on_duplicate_transition=duplicate_transition_add_input)
sage: assume(p + q == 1)
sage: (p + q - 1).is_zero()
True
sage: F.is_Markov_chain()
True
sage: forget()
sage: del(p, q)

If the probabilities are variables in some polynomial ring, the parameter is_zero can be used:

sage: R.<p, q> = PolynomialRing(QQ)
sage: def is_zero_polynomial(polynomial):
....:     return polynomial in (p + q - 1)*R
sage: F = Transducer([(0, 0, p, 1), (0, 0, q, 0)],
....:                on_duplicate_transition=duplicate_transition_add_input)
sage: F.is_Markov_chain()
False
sage: F.is_Markov_chain(is_zero_polynomial)
True
is_complete()

Returns whether the finite state machine is complete.

INPUT:

Nothing.

OUTPUT:

True or False.

A finite state machine is considered to be complete if each transition has an 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 exactly one transition from \(q\) with input label \(a\).

EXAMPLES:

sage: fsm = FiniteStateMachine([(0, 0, 0, 0),
....:                           (0, 1, 1, 1),
....:                           (1, 1, 0, 0)],
....:                          determine_alphabets=False)
sage: fsm.is_complete()
Traceback (most recent call last):
...
ValueError: No input alphabet is given. Try calling determine_alphabets().
sage: fsm.input_alphabet = [0, 1]
sage: fsm.is_complete()
False
sage: fsm.add_transition((1, 1, 1, 1))
Transition from 1 to 1: 1|1
sage: fsm.is_complete()
True
sage: fsm.add_transition((0, 0, 1, 0))
Transition from 0 to 0: 1|0
sage: fsm.is_complete()
False
is_connected()

TESTS:

sage: FiniteStateMachine().is_connected()
Traceback (most recent call last):
...
NotImplementedError
is_deterministic()

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
is_monochromatic()

Checks whether the colors of all states are equal.

INPUT:

Nothing.

OUTPUT:

True or False.

EXAMPLES:

sage: G = transducers.GrayCode()
sage: [s.color for s in G.iter_states()]
[None, None, None]
sage: G.is_monochromatic()
True
sage: G.state(1).color = 'blue'
sage: G.is_monochromatic()
False
iter_final_states()

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']
iter_initial_states()

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']
iter_process(input_tape=None, initial_state=None, **kwargs)

This function returns an instance of FSMProcessIterator. See process() (which runs this iterator until the end) for more information.

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 current in it:
....:     print current
process (1 branch)
+ at state 'A'
+-- tape at 1, [[1]]
process (1 branch)
+ at state 'A'
+-- tape at 2, [[1, 0]]
process (1 branch)
+ at state 'A'
+-- tape at 3, [[1, 0, 0]]
process (0 branches)
sage: it.result()
[(True, 'A', [1, 0, 0])]
iter_states()

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']
iter_transitions(from_state=None)

Returns an iterator of all transitions.

INPUT:

  • from_state – (default: None) If from_state is given, then a list of transitions starting there is given.

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')]
latex_options(coordinates=None, format_state_label=None, format_letter=None, format_transition_label=None, loop_where=None, initial_where=None, accepting_style=None, accepting_distance=None, accepting_where=None, accepting_show_empty=None)

Set options for LaTeX output via latex() and therefore view().

INPUT:

  • coordinates – a dictionary or a function mapping labels of states to pairs interpreted as coordinates. If no coordinates are given, states a placed equidistantly on a circle of radius \(3\). See also set_coordinates().
  • format_state_label – a function mapping labels of states to a string suitable for typesetting in LaTeX’s mathematics mode. If not given, latex() is used.
  • format_letter – a function mapping letters of the input and output alphabets to a string suitable for typesetting in LaTeX’s mathematics mode. If not given, default_format_transition_label() uses latex().
  • format_transition_label – a function mapping words over the input and output alphabets to a string suitable for typesetting in LaTeX’s mathematics mode. If not given, default_format_transition_label() is used.
  • loop_where – a dictionary or a function mapping labels of initial states to one of 'above', 'left', 'below', 'right'. If not given, 'above' is used.
  • initial_where – a dictionary or a function mapping labels of initial states to one of 'above', 'left', 'below', 'right'. If not given, TikZ’ default (currently 'left') is used.
  • accepting_style – one of 'accepting by double' and 'accepting by arrow'. If not given, 'accepting by double' is used unless there are non-empty final output words.
  • accepting_distance – a string giving a LaTeX length used for the length of the arrow leading from a final state. If not given, TikZ’ default (currently '3ex') is used unless there are non-empty final output words, in which case '7ex' is used.
  • accepting_where – a dictionary or a function mapping labels of final states to one of 'above', 'left', 'below', 'right'. If not given, TikZ’ default (currently 'right') is used. If the final state has a final output word, it is also possible to give an angle in degrees.
  • accepting_show_empty – if True the arrow of an empty final output word is labeled as well. Note that this implicitly implies accepting_style='accepting by arrow'. If not given, the default False is used.

OUTPUT:

Nothing.

As TikZ (cf. the Wikipedia article PGF/TikZ) is used to typeset the graphics, the syntax is oriented on TikZ’ syntax.

This is a convenience function collecting all options for LaTeX output. All of its functionality can also be achieved by directly setting the attributes

  • coordinates, format_label, loop_where, initial_where, and accepting_where of FSMState (here, format_label is a callable without arguments, everything else is a specific value);
  • format_label of FSMTransition (format_label is a callable without arguments);
  • format_state_label, format_letter, format_transition_label, accepting_style, accepting_distance, and accepting_show_empty of FiniteStateMachine.

This function, however, also (somewhat) checks its input and serves to collect documentation on all these options.

The function can be called several times, only those arguments which are not None are taken into account. By the same means, it can be combined with directly setting some attributes as outlined above.

EXAMPLES:

See also the section on LaTeX output in the introductory examples of this module.

sage: T = Transducer(initial_states=[4],
....:     final_states=[0, 3])
sage: for j in srange(4):
....:     T.add_transition(4, j, 0, [0, j])
....:     T.add_transition(j, 4, 0, [0, -j])
....:     T.add_transition(j, j, 0, 0)
Transition from 4 to 0: 0|0,0
Transition from 0 to 4: 0|0,0
Transition from 0 to 0: 0|0
Transition from 4 to 1: 0|0,1
Transition from 1 to 4: 0|0,-1
Transition from 1 to 1: 0|0
Transition from 4 to 2: 0|0,2
Transition from 2 to 4: 0|0,-2
Transition from 2 to 2: 0|0
Transition from 4 to 3: 0|0,3
Transition from 3 to 4: 0|0,-3
Transition from 3 to 3: 0|0
sage: T.add_transition(4, 4, 0, 0)
Transition from 4 to 4: 0|0
sage: T.state(3).final_word_out = [0, 0]
sage: T.latex_options(
....:     coordinates={4: (0, 0),
....:                  0: (-6, 3),
....:                  1: (-2, 3),
....:                  2: (2, 3),
....:                  3: (6, 3)},
....:     format_state_label=lambda x: r'\mathbf{%s}' % x,
....:     format_letter=lambda x: r'w_{%s}' % x,
....:     format_transition_label=lambda x:
....:         r"{\scriptstyle %s}" % T.default_format_transition_label(x),
....:     loop_where={4: 'below', 0: 'left', 1: 'above',
....:                 2: 'right', 3:'below'},
....:     initial_where=lambda x: 'above',
....:     accepting_style='accepting by double',
....:     accepting_distance='10ex',
....:     accepting_where={0: 'left', 3: 45}
....:     )
sage: T.state(4).format_label=lambda: r'\mathcal{I}'
sage: latex(T)
\begin{tikzpicture}[auto, initial text=, >=latex]
\node[state, initial, initial where=above] (v0) at (0.000000, 0.000000) {$\mathcal{I}$};
\node[state, accepting, accepting where=left] (v1) at (-6.000000, 3.000000) {$\mathbf{0}$};
\node[state, accepting, accepting where=45] (v2) at (6.000000, 3.000000) {$\mathbf{3}$};
\path[->] (v2.45.00) edge node[rotate=45.00, anchor=south] {$$ \mid {\scriptstyle w_{0} w_{0}}$} ++(45.00:10ex);
\node[state] (v3) at (-2.000000, 3.000000) {$\mathbf{1}$};
\node[state] (v4) at (2.000000, 3.000000) {$\mathbf{2}$};
\path[->] (v1) edge[loop left] node[rotate=90, anchor=south] {${\scriptstyle w_{0}}\mid {\scriptstyle w_{0}}$} ();
\path[->] (v1.-21.57) edge node[rotate=-26.57, anchor=south] {${\scriptstyle w_{0}}\mid {\scriptstyle w_{0} w_{0}}$} (v0.148.43);
\path[->] (v3) edge[loop above] node {${\scriptstyle w_{0}}\mid {\scriptstyle w_{0}}$} ();
\path[->] (v3.-51.31) edge node[rotate=-56.31, anchor=south] {${\scriptstyle w_{0}}\mid {\scriptstyle w_{0} w_{-1}}$} (v0.118.69);
\path[->] (v4) edge[loop right] node[rotate=90, anchor=north] {${\scriptstyle w_{0}}\mid {\scriptstyle w_{0}}$} ();
\path[->] (v4.-118.69) edge node[rotate=56.31, anchor=north] {${\scriptstyle w_{0}}\mid {\scriptstyle w_{0} w_{-2}}$} (v0.51.31);
\path[->] (v2) edge[loop below] node {${\scriptstyle w_{0}}\mid {\scriptstyle w_{0}}$} ();
\path[->] (v2.-148.43) edge node[rotate=26.57, anchor=north] {${\scriptstyle w_{0}}\mid {\scriptstyle w_{0} w_{-3}}$} (v0.21.57);
\path[->] (v0.158.43) edge node[rotate=333.43, anchor=north] {${\scriptstyle w_{0}}\mid {\scriptstyle w_{0} w_{0}}$} (v1.328.43);
\path[->] (v0.128.69) edge node[rotate=303.69, anchor=north] {${\scriptstyle w_{0}}\mid {\scriptstyle w_{0} w_{1}}$} (v3.298.69);
\path[->] (v0.61.31) edge node[rotate=56.31, anchor=south] {${\scriptstyle w_{0}}\mid {\scriptstyle w_{0} w_{2}}$} (v4.231.31);
\path[->] (v0.31.57) edge node[rotate=26.57, anchor=south] {${\scriptstyle w_{0}}\mid {\scriptstyle w_{0} w_{3}}$} (v2.201.57);
\path[->] (v0) edge[loop below] node {${\scriptstyle w_{0}}\mid {\scriptstyle w_{0}}$} ();
\end{tikzpicture}
sage: view(T) # not tested

To actually see this, use the live documentation in the Sage notebook and execute the cells.

By changing some of the options, we get the following output:

sage: T.latex_options(
....:     format_transition_label=T.default_format_transition_label,
....:     accepting_style='accepting by arrow',
....:     accepting_show_empty=True
....:     )
sage: latex(T)
\begin{tikzpicture}[auto, initial text=, >=latex, accepting text=, accepting/.style=accepting by arrow, accepting distance=10ex]
\node[state, initial, initial where=above] (v0) at (0.000000, 0.000000) {$\mathcal{I}$};
\node[state] (v1) at (-6.000000, 3.000000) {$\mathbf{0}$};
\path[->] (v1.180.00) edge node[rotate=360.00, anchor=south] {$$ \mid \varepsilon$} ++(180.00:10ex);
\node[state] (v2) at (6.000000, 3.000000) {$\mathbf{3}$};
\path[->] (v2.45.00) edge node[rotate=45.00, anchor=south] {$$ \mid w_{0} w_{0}$} ++(45.00:10ex);
\node[state] (v3) at (-2.000000, 3.000000) {$\mathbf{1}$};
\node[state] (v4) at (2.000000, 3.000000) {$\mathbf{2}$};
\path[->] (v1) edge[loop left] node[rotate=90, anchor=south] {$w_{0}\mid w_{0}$} ();
\path[->] (v1.-21.57) edge node[rotate=-26.57, anchor=south] {$w_{0}\mid w_{0} w_{0}$} (v0.148.43);
\path[->] (v3) edge[loop above] node {$w_{0}\mid w_{0}$} ();
\path[->] (v3.-51.31) edge node[rotate=-56.31, anchor=south] {$w_{0}\mid w_{0} w_{-1}$} (v0.118.69);
\path[->] (v4) edge[loop right] node[rotate=90, anchor=north] {$w_{0}\mid w_{0}$} ();
\path[->] (v4.-118.69) edge node[rotate=56.31, anchor=north] {$w_{0}\mid w_{0} w_{-2}$} (v0.51.31);
\path[->] (v2) edge[loop below] node {$w_{0}\mid w_{0}$} ();
\path[->] (v2.-148.43) edge node[rotate=26.57, anchor=north] {$w_{0}\mid w_{0} w_{-3}$} (v0.21.57);
\path[->] (v0.158.43) edge node[rotate=333.43, anchor=north] {$w_{0}\mid w_{0} w_{0}$} (v1.328.43);
\path[->] (v0.128.69) edge node[rotate=303.69, anchor=north] {$w_{0}\mid w_{0} w_{1}$} (v3.298.69);
\path[->] (v0.61.31) edge node[rotate=56.31, anchor=south] {$w_{0}\mid w_{0} w_{2}$} (v4.231.31);
\path[->] (v0.31.57) edge node[rotate=26.57, anchor=south] {$w_{0}\mid w_{0} w_{3}$} (v2.201.57);
\path[->] (v0) edge[loop below] node {$w_{0}\mid w_{0}$} ();
\end{tikzpicture}
sage: view(T) # not tested

TESTS:

sage: T.latex_options(format_state_label='Nothing')
Traceback (most recent call last):
...
TypeError: format_state_label must be callable.
sage: T.latex_options(format_letter='')
Traceback (most recent call last):
...
TypeError: format_letter must be callable.
sage: T.latex_options(format_transition_label='')
Traceback (most recent call last):
...
TypeError: format_transition_label must be callable.
sage: T.latex_options(loop_where=37)
Traceback (most recent call last):
...
TypeError: loop_where must be a callable or a
dictionary.
sage: T.latex_options(loop_where=lambda x: 'top')
Traceback (most recent call last):
...
ValueError: loop_where for 4 must be in ['below',
'right', 'above', 'left'].
sage: T.latex_options(initial_where=90)
Traceback (most recent call last):
...
TypeError: initial_where must be a callable or a
dictionary.
sage: T.latex_options(initial_where=lambda x: 'top')
Traceback (most recent call last):
...
ValueError: initial_where for 4 must be in ['below',
'right', 'above', 'left'].
sage: T.latex_options(accepting_style='fancy')
Traceback (most recent call last):
...
ValueError: accepting_style must be in ['accepting by
double', 'accepting by arrow'].
sage: T.latex_options(accepting_where=90)
Traceback (most recent call last):
...
TypeError: accepting_where must be a callable or a
dictionary.
sage: T.latex_options(accepting_where=lambda x: 'top')
Traceback (most recent call last):
...
ValueError: accepting_where for 0 must be in ['below',
'right', 'above', 'left'].
sage: T.latex_options(accepting_where={0: 'above', 3: 'top'})
Traceback (most recent call last):
...
ValueError: accepting_where for 3 must be a real number or
be in ['below', 'right', 'above', 'left'].
markov_chain_simplification()

Consider self as Markov chain with probabilities as input labels and simplify it.

INPUT:

Nothing.

OUTPUT:

Simplified version of self.

EXAMPLE:

sage: from sage.combinat.finite_state_machine import duplicate_transition_add_input
sage: T = Transducer([[1, 2, 1/4, 0], [1, -2, 1/4, 0], [1, -2, 1/2, 0],
....:                 [2, 2, 1/4, 1], [2, -2, 1/4, 1], [-2, -2, 1/4, 1],
....:                 [-2, 2, 1/4, 1], [2, 3, 1/2, 2], [-2, 3, 1/2, 2]],
....:                initial_states=[1],
....:                final_states=[3],
....:                on_duplicate_transition=duplicate_transition_add_input)
sage: T1 = T.markov_chain_simplification()
sage: sorted(T1.transitions())
[Transition from ((1,),) to ((2, -2),): 1|0,
 Transition from ((2, -2),) to ((2, -2),): 1/2|1,
 Transition from ((2, -2),) to ((3,),): 1/2|2]
merged_transitions()

Merges transitions which have the same from_state, to_state and word_out while adding their word_in.

INPUT:

Nothing.

OUTPUT:

A finite state machine with merged transitions. If no mergers occur, return self.

EXAMPLE:

sage: from sage.combinat.finite_state_machine import duplicate_transition_add_input
sage: T = Transducer([[1, 2, 1/4, 1], [1, -2, 1/4, 1], [1, -2, 1/2, 1],
....:                 [2, 2, 1/4, 1], [2, -2, 1/4, 1], [-2, -2, 1/4, 1],
....:                 [-2, 2, 1/4, 1], [2, 3, 1/2, 1], [-2, 3, 1/2, 1]],
....:                on_duplicate_transition=duplicate_transition_add_input)
sage: T1 = T.merged_transitions()
sage: T1 is T
False
sage: sorted(T1.transitions())
[Transition from -2 to -2: 1/4|1,
 Transition from -2 to 2: 1/4|1,
 Transition from -2 to 3: 1/2|1,
 Transition from 1 to 2: 1/4|1,
 Transition from 1 to -2: 3/4|1,
 Transition from 2 to -2: 1/4|1,
 Transition from 2 to 2: 1/4|1,
 Transition from 2 to 3: 1/2|1]

Applying the function again does not change the result:

sage: T2 = T1.merged_transitions()
sage: T2 is T1
True
on_duplicate_transition(old_transition, new_transition)

Which function to call when a duplicate transition is inserted. See the documentation of the parameter on_duplicate_transition of the class FiniteStateMachine for details.

output_projection()

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|-]

Final output words are also considered correctly:

sage: H = Transducer([('A', 'B', 0, 1), ('A', 'A', 1, 1),
....:                 ('B', 'B', 1, 0), ('A', ('final', 0), 0, 0)],
....:                final_states=['A', 'B'])
sage: H.state('B').final_word_out = 2
sage: J = H.output_projection()
sage: J.states()
['A', 'B', ('final', 0), ('final', 1)]
sage: J.transitions()
[Transition from 'A' to 'B': 1|-,
 Transition from 'A' to 'A': 1|-,
 Transition from 'A' to ('final', 0): 0|-,
 Transition from 'B' to 'B': 0|-,
 Transition from 'B' to ('final', 1): 2|-]
sage: J.final_states()
['A', ('final', 1)]
plot()

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()
Graphics object consisting of 3 graphics primitives
predecessors(state, valid_input=None)

Lists all predecessors of a state.

INPUT:

  • state – the state from which the predecessors should be listed.
  • valid_input – If valid_input is a list, then we only consider transitions whose input labels are contained in valid_input. state has to be a FSMState (not a label of a state). If input labels of length larger than \(1\) are used, then valid_input has to be a list of lists.

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']
prepone_output()

For all paths, shift the output of the path from one transition to the earliest possible preceeding transition of the path.

INPUT:

Nothing.

OUTPUT:

Nothing.

Apply the following to each state \(s\) (except initial states) of the finite state machine as often as possible:

If the letter \(a\) is a prefix of the output label of all transitions from \(s\) (including the final output of \(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, but final outputs are allowed.

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()
verbose 0 (...: finite_state_machine.py, 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|-]

Also the final output of final states can be changed:

sage: T = Transducer([('A', 'B', 0, 1),
....:                 ('B', 'C', 1, [1, 1]),
....:                 ('B', 'C', 0, 1)],
....:                initial_states=['A'],
....:                final_states=['B'])
sage: T.state('B').final_word_out = [1]
sage: T.prepone_output()
sage: T.transitions()
[Transition from 'A' to 'B': 0|1,1,
 Transition from 'B' to 'C': 1|1,
 Transition from 'B' to 'C': 0|-]
sage: T.state('B').final_word_out
[]
sage: S = Transducer([('A', 'B', 0, 1),
....:                 ('B', 'C', 1, [1, 1]),
....:                 ('B', 'C', 0, 1)],
....:                initial_states=['A'],
....:                final_states=['B'])
sage: S.state('B').final_word_out = [0]
sage: S.prepone_output()
sage: S.transitions()
[Transition from 'A' to 'B': 0|1,
 Transition from 'B' to 'C': 1|1,1,
 Transition from 'B' to 'C': 0|1]
sage: S.state('B').final_word_out
[0]

Output labels do not have to be hashable:

sage: C = Transducer([(0, 1, 0, []),
....:                 (1, 0, 0, [vector([0, 0]), 0]),
....:                 (1, 1, 1, [vector([0, 0]), 1]),
....:                 (0, 0, 1, 0)],
....:                 determine_alphabets=False,
....:                 initial_states=[0])
sage: C.prepone_output()
sage: sorted(C.transitions())
[Transition from 0 to 1: 0|(0, 0),
 Transition from 0 to 0: 1|0,
 Transition from 1 to 0: 0|0,
 Transition from 1 to 1: 1|1,(0, 0)]
process(*args, **kwargs)

Returns whether the finite state machine accepts the input, the state where the computation stops and which output is generated.

INPUT:

  • input_tape – the input tape can be a list or an iterable with entries from the input alphabet. If we are working with a multi-tape machine (see parameter use_multitape_input and notes below), then the tape is a list or tuple of tracks, each of which can be a list or an iterable with entries from the input alphabet.
  • initial_state or initial_states – the initial state(s) in which the machine starts. Either specify a single one with initial_state or a list of them with initial_states. If both are given, initial_state will be appended to initial_states. If neither is specified, the initial states of the finite state machine are taken.
  • list_of_outputs – (default: None) a boolean or None. If True, then the outputs are given in list form (even if we have no or only one single output). If False, then the result is never a list (an exception is raised if the result cannot be returned). If list_of_outputs=None, the method determines automatically what to do (e.g. if a non-deterministic machine returns more than one path, then the output is returned in list form).
  • only_accepted – (default: False) a boolean. If set, then the first argument in the output is guaranteed to be True (if the output is a list, then the first argument of each element will be True).
  • always_include_output – if set (not by default), always include the output. This is inconsequential for a FiniteStateMachine, but can be used in derived classes where the output is suppressed by default, cf. Automaton.process().
  • format_output – a function that translates the written output (which is in form of a list) to something more readable. By default (None) identity is used here.
  • check_epsilon_transitions – (default: True) a boolean. If False, then epsilon transitions are not taken into consideration during process.
  • write_final_word_out – (default: True) a boolean specifying whether the final output words should be written or not.
  • use_multitape_input – (default: False) a boolean. If True, then the multi-tape mode of the process iterator is activated. See also the notes below for multi-tape machines.

OUTPUT:

A triple (or a list of triples, cf. parameter list_of_outputs), where

  • the first entry is True if the input string is accepted,
  • the second gives the reached state after processing the input tape (This is a state with label None if the input could not be processed, i.e., if at one point no transition to go on could be found.), and
  • the third gives a list of the output labels written during processing (in the case the finite state machine runs as transducer).

Note that in the case the finite state machine is not deterministic, all possible paths are taken into account.

This function uses an iterator which, in its simplest form, goes from one state to another in each step. To decide which way to go, it uses the input words of the outgoing transitions and compares them to the input tape. More precisely, in each step, the 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.

If the choice of the outgoing transition is not unique (i.e., we have a non-deterministic finite state machine), all possibilites are followed. This is done by splitting the process into several branches, one for each of the possible outgoing transitions.

The process (iteration) stops if all branches are finished, i.e., for no branch, there is any transition whose input word coincides with the processed input tape. This can simply happen when the entire tape was read.

Also see __call__() for a version of process() with shortened output.

Internally this function creates and works with an instance of FSMProcessIterator. This iterator can also be obtained with iter_process().

If working with multi-tape finite state machines, all input words of transitions are words of \(k\)-tuples of letters. Moreover, the input tape has to consist of \(k\) tracks, i.e., be a list or tuple of \(k\) iterators, one for each track.

Warning

Working with multi-tape finite state machines is still experimental and can lead to wrong outputs.

EXAMPLES:

sage: binary_inverter = FiniteStateMachine({'A': [('A', 0, 1), ('A', 1, 0)]},
....:                                      initial_states=['A'], final_states=['A'])
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])

Below we construct a finite state machine which tests if an input is a non-adjacent form, i.e., no two neighboring letters are both nonzero (see also the example on non-adjacent forms in the documentation of the module finite_state_machine):

sage: NAF = FiniteStateMachine(
....:     {'_': [('_', 0), (1, 1)], 1: [('_', 0)]},
....:     initial_states=['_'], final_states=['_', 1])
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]

Working only with the first component (i.e., returning whether accepted or not) usually corresponds to using the more specialized class Automaton.

Non-deterministic finite state machines can be handeled as well.

sage: T = Transducer([(0, 1, 0, 0), (0, 2, 0, 0)],
....:     initial_states=[0])
sage: T.process([0])
[(False, 1, [0]), (False, 2, [0])]

Here is another non-deterministic finite state machine. Note that we use format_output (see FSMProcessIterator) to convert the written outputs (all characters) to strings.

sage: T = Transducer([(0, 1, [0, 0], 'a'), (0, 2, [0, 0, 1], 'b'),
....:                 (0, 1, 1, 'c'), (1, 0, [], 'd'),
....:                 (1, 1, 1, 'e')],
....:                initial_states=[0], final_states=[0, 1])
sage: T.process([0], format_output=lambda o: ''.join(o))
(False, None, None)
sage: T.process([0, 0], format_output=lambda o: ''.join(o))
[(True, 0, 'ad'), (True, 1, 'a')]
sage: T.process([1], format_output=lambda o: ''.join(o))
[(True, 0, 'cd'), (True, 1, 'c')]
sage: T.process([1, 1], format_output=lambda o: ''.join(o))
[(True, 0, 'cdcd'), (True, 0, 'ced'),
 (True, 1, 'cdc'), (True, 1, 'ce')]
sage: T.process([0, 0, 1], format_output=lambda o: ''.join(o))
[(True, 0, 'adcd'), (True, 0, 'aed'),
 (True, 1, 'adc'), (True, 1, 'ae'), (False, 2, 'b')]
sage: T.process([0, 0, 1], format_output=lambda o: ''.join(o),
....:           only_accepted=True)
[(True, 0, 'adcd'), (True, 0, 'aed'),
 (True, 1, 'adc'), (True, 1, 'ae')]

A simple example of a multi-tape finite state machine is the following: It writes the length of the first tape many letters a and then the length of the second tape many letters b:

sage: M = FiniteStateMachine([(0, 0, (1, None), 'a'),
....:                         (0, 1, [], []),
....:                         (1, 1, (None, 1), 'b')],
....:                        initial_states=[0],
....:                        final_states=[1])
sage: M.process(([1, 1], [1]), use_multitape_input=True)
(True, 1, ['a', 'a', 'b'])

TESTS:

sage: T = Transducer([(0, 1, [0, 0], 0), (0, 2, [0, 0, 1], 0),
....:                 (0, 1, 1, 2), (1, 0, [], 1), (1, 1, 1, 3)],
....:     initial_states=[0], final_states=[0, 1])
sage: T.process([0])
(False, None, None)
sage: T.process([0, 0])
[(True, 0, [0, 1]), (True, 1, [0])]
sage: T.process([1])
[(True, 0, [2, 1]), (True, 1, [2])]
sage: T.process([1, 1])
[(True, 0, [2, 1, 2, 1]), (True, 0, [2, 3, 1]),
 (True, 1, [2, 1, 2]), (True, 1, [2, 3])]
sage: F = FiniteStateMachine([(0, 0, 0, 0)],
....:                        initial_states=[0])
sage: F.process([0], only_accepted=True)
[]
sage: F.process([0], only_accepted=True, list_of_outputs=False)
Traceback (most recent call last):
...
ValueError: No accepting output was found but according to the
given options, an accepting output should be returned. Change
only_accepted and/or list_of_outputs options.
sage: F.process([0], only_accepted=True, list_of_outputs=True)
[]
sage: F.process([0], only_accepted=False)
(False, 0, [0])
sage: F.process([0], only_accepted=False, list_of_outputs=False)
(False, 0, [0])
sage: F.process([0], only_accepted=False, list_of_outputs=True)
[(False, 0, [0])]
sage: F.process([1], only_accepted=True)
[]
sage: F.process([1], only_accepted=True, list_of_outputs=False)
Traceback (most recent call last):
...
ValueError: No accepting output was found but according to the
given options, an accepting output should be returned. Change
only_accepted and/or list_of_outputs options.
sage: F.process([1], only_accepted=True, list_of_outputs=True)
[]
sage: F.process([1], only_accepted=False)
(False, None, None)
sage: F.process([1], only_accepted=False, list_of_outputs=False)
(False, None, None)
sage: F.process([1], only_accepted=False, list_of_outputs=True)
[]
sage: F = FiniteStateMachine([(0, 1, 1, 'a'), (0, 2, 2, 'b')],
....:                        initial_states=[0],
....:                        final_states=[1])
sage: A = Automaton([(0, 1, 1), (0, 2, 2)],
....:               initial_states=[0],
....:               final_states=[1])
sage: T = Transducer([(0, 1, 1, 'a'), (0, 2, 2, 'b')],
....:                initial_states=[0],
....:                final_states=[1])
sage: F.process([1])
(True, 1, ['a'])
sage: A.process([1])
(True, 1)
sage: T.process([1])
(True, 1, ['a'])
sage: F.process([2])
(False, 2, ['b'])
sage: A.process([2])
(False, 2)
sage: T.process([2])
(False, 2, ['b'])
sage: F.process([3])
(False, None, None)
sage: A.process([3])
(False, None)
sage: T.process([3])
(False, None, None)
product_FiniteStateMachine(other, function, new_input_alphabet=None, only_accessible_components=True, final_function=None, new_class=None)

Returns a new finite state machine whose states are \(d\)-tuples of states of the original finite state machines.

INPUT:

  • other – a finite state machine (for \(d=2\)) or a list (or iterable) of \(d-1\) finite state machines.
  • function has to accept \(d\) transitions from \(A_j\) to \(B_j\) for \(j\in\{1, \ldots, d\}\) and returns a pair (word_in, word_out) which is the label of the transition \(A=(A_1, \ldots, A_d)\) to \(B=(B_1, \ldots, B_d)\). If there is no transition from \(A\) to \(B\), then function should raise a LookupError.
  • new_input_alphabet (optional) – the new input alphabet as a list.
  • only_accessible_components – If True (default), then the result is piped through accessible_components(). If no new_input_alphabet is given, it is determined by determine_alphabets().
  • final_function – A function mapping \(d\) final states of the original finite state machines to the final output of the corresponding state in the new finite state machine. By default, the final output is the empty word if both final outputs of the constituent states are empty; otherwise, a ValueError is raised.
  • new_class – Class of the new finite state machine. By default (None), the class of self is used.

OUTPUT:

A finite state machine whose states are \(d\)-tuples of states of the original finite state machines. A state is initial or final if all constituent states are initial or final, respectively.

The labels of the transitions are defined by function.

The final output of a final state is determined by calling final_function on the constituent states.

The color of a new state is the tuple of colors of the constituent states of self and other.

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)]

Also final output words are considered according to the function final_function:

sage: F = Transducer([(0, 1, 0, 1), (1, 1, 1, 1), (1, 1, 0, 1)],
....:                final_states=[1])
sage: F.state(1).final_word_out = 1
sage: G = Transducer([(0, 0, 0, 1), (0, 0, 1, 0)], final_states=[0])
sage: G.state(0).final_word_out = 1
sage: def minus(t1, t2):
....:     return (t1.word_in[0] - t2.word_in[0],
....:                t1.word_out[0] - t2.word_out[0])
sage: H = F.product_FiniteStateMachine(G, minus)
Traceback (most recent call last):
...
ValueError: A final function must be given.
sage: def plus(s1, s2):
....:     return s1.final_word_out[0] + s2.final_word_out[0]
sage: H = F.product_FiniteStateMachine(G, minus,
....:                                  final_function=plus)
sage: H.final_states()
[(1, 0)]
sage: H.final_states()[0].final_word_out
[2]

Products of more than two finite state machines are also possible:

sage: def plus(s1, s2, s3):
....:     if s1.word_in == s2.word_in == s3.word_in:
....:          return (s1.word_in,
....:                  sum(s.word_out[0] for s in (s1, s2, s3)))
....:     else:
....:         raise LookupError
sage: T0 = transducers.CountSubblockOccurrences([0, 0], [0, 1, 2])
sage: T1 = transducers.CountSubblockOccurrences([1, 1], [0, 1, 2])
sage: T2 = transducers.CountSubblockOccurrences([2, 2], [0, 1, 2])
sage: T = T0.product_FiniteStateMachine([T1, T2], plus)
sage: T.transitions()
[Transition from ((), (), ()) to ((0,), (), ()): 0|0,
 Transition from ((), (), ()) to ((), (1,), ()): 1|0,
 Transition from ((), (), ()) to ((), (), (2,)): 2|0,
 Transition from ((0,), (), ()) to ((0,), (), ()): 0|1,
 Transition from ((0,), (), ()) to ((), (1,), ()): 1|0,
 Transition from ((0,), (), ()) to ((), (), (2,)): 2|0,
 Transition from ((), (1,), ()) to ((0,), (), ()): 0|0,
 Transition from ((), (1,), ()) to ((), (1,), ()): 1|1,
 Transition from ((), (1,), ()) to ((), (), (2,)): 2|0,
 Transition from ((), (), (2,)) to ((0,), (), ()): 0|0,
 Transition from ((), (), (2,)) to ((), (1,), ()): 1|0,
 Transition from ((), (), (2,)) to ((), (), (2,)): 2|1]
sage: T([0, 0, 1, 1, 2, 2, 0, 1, 2, 2])
[0, 1, 0, 1, 0, 1, 0, 0, 0, 1]

other can also be an iterable:

sage: T == T0.product_FiniteStateMachine(iter([T1, T2]), plus)
True

TESTS:

Check that colors are correctly dealt with. In particular, the new colors have to be hashable such that Automaton.determinisation() does not fail:

sage: A = Automaton([[0, 0, 0]], initial_states=[0])
sage: B = A.product_FiniteStateMachine(A,
....:                                  lambda t1, t2: (0, None))
sage: B.states()[0].color
(None, None)
sage: B.determinisation()
Automaton with 1 states

Check handling of the parameter other:

sage: A.product_FiniteStateMachine(None, plus)
Traceback (most recent call last):
...
ValueError: other must be a finite state machine or a list
of finite state machines.
sage: A.product_FiniteStateMachine([None], plus)
Traceback (most recent call last):
...
ValueError: other must be a finite state machine or a list
of finite state machines.

Test whether new_class works:

sage: T = Transducer()
sage: type(T.product_FiniteStateMachine(T, None))
<class 'sage.combinat.finite_state_machine.Transducer'>
sage: type(T.product_FiniteStateMachine(T, None,
....:      new_class=Automaton))
<class 'sage.combinat.finite_state_machine.Automaton'>

Check that isolated vertices are kept (trac ticket #16762):

sage: F = Transducer(initial_states=[0])
sage: F.add_state(1)
1
sage: G = Transducer(initial_states=['A'])
sage: F.product_FiniteStateMachine(G, None).states()
[(0, 'A')]
sage: F.product_FiniteStateMachine(
....:     G, None, only_accessible_components=False).states()
[(0, 'A'), (1, 'A')]
projection(what='input')

Returns an Automaton which transition labels are the projection of the transition labels of the input.

INPUT:

  • what – (default: input) either input or output.

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|-]
quotient(classes)

Constructs the quotient with respect to the equivalence classes.

INPUT:

  • classes is a list of equivalence classes of states.

OUTPUT:

A finite state machine.

The labels of the new states are tuples of states of the self, corresponding to classes.

Assume that \(c\) is a class, and \(a\) and \(b\) are states in \(c\). Then there is a bijection \(\varphi\) between the transitions from \(a\) and the transitions from \(b\) with the following properties: if \(\varphi(t_a)=t_b\), then

  • \(t_a.\mathit{word}_\mathit{in}=t_b.\mathit{word}_\mathit{in}\),
  • \(t_a.\mathit{word}_\mathit{out}=t_b.\mathit{word}_\mathit{out}\), and
  • \(t_a\) and \(t_b\) lead to some equivalent states \(a'\) and \(b'\).

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, final_word_out 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):
    ...
AssertionError: Transitions of state 'A' and 'B' are incompatible.

TESTS:

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)],
....:                           final_states=["A", "C"])
sage: fsm.state("A").final_word_out = 1
sage: fsm.state("C").final_word_out = 2
sage: fsmq = fsm.quotient([[fsm.state("A"), fsm.state("C")],
....:                      [fsm.state("B"), fsm.state("D")]])
Traceback (most recent call last):
    ...
AssertionError: Class ['A', 'C'] mixes
final states with different final output words.
relabeled(memo=None, labels=None)

Returns a deep copy of the finite state machine, but the states are relabeled.

INPUT:

  • memo – (default: None) a dictionary storing already processed elements.
  • labels – (default: None) a dictionary or callable mapping old labels to new labels. If None, then the new labels are integers starting with 0.

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]
sage: FSM3 = FSM1.relabeled(labels={'A': 'a', 'B': 'b', 'C': 'c'})
sage: FSM3.states()
['a', 'b', 'c']
sage: FSM4 = FSM2.relabeled(labels=lambda x: 2*x)
sage: FSM4.states()
[0, 2, 4]

TESTS:

sage: FSM2.relabeled(labels=1)
Traceback (most recent call last):
...
TypeError: labels must be None, a callable or a dictionary.
remove_epsilon_transitions()

TESTS:

sage: FiniteStateMachine().remove_epsilon_transitions()
Traceback (most recent call last):
...
NotImplementedError
set_coordinates(coordinates, default=True)

Set coordinates of the states for the LaTeX representation by a dictionary or a function mapping labels to coordinates.

INPUT:

  • coordinates – a dictionary or a function mapping labels of states to pairs interpreted as coordinates.
  • default – If True, then states not given by coordinates get a default position on a circle of radius 3.

OUTPUT:

Nothing.

EXAMPLES:

sage: F = Automaton([[0, 1, 1], [1, 2, 2], [2, 0, 0]])
sage: F.set_coordinates({0: (0, 0), 1: (2, 0), 2: (1, 1)})
sage: F.state(0).coordinates
(0, 0)

We can also use a function to determine the coordinates:

sage: F = Automaton([[0, 1, 1], [1, 2, 2], [2, 0, 0]])
sage: F.set_coordinates(lambda l: (l, 3/(l+1)))
sage: F.state(2).coordinates
(2, 1)
split_transitions()

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))]
state(state)

Returns the state of the finite state machine.

INPUT:

  • state – If state is not an instance of FSMState, then it is assumed that it is the label of a state.

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.
states()

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']
transition(transition)

Returns the transition of the finite state machine.

INPUT:

  • transition – If transition is not an instance of FSMTransition, then it is assumed that it is a tuple (from_state, to_state, word_in, word_out).

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
transitions(from_state=None)

Returns a list of all transitions.

INPUT:

  • from_state – (default: None) If from_state is given, then a list of transitions starting there is given.

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|-]
transposition()

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']

TESTS:

If a final state of self has a non-empty final output word, transposition is not implemented:

sage: T = Transducer([('1', '1', 1, 0), ('1', '2', 0, 1),
....:                 ('2', '2', 0, 2)],
....:                 initial_states=['1'],
....:                 final_states=['1', '2'])
sage: T.state('1').final_word_out = [2, 5]
sage: T.transposition()
Traceback (most recent call last):
...
NotImplementedError: Transposition for transducers with
final output words is not implemented.
with_final_word_out(letters, allow_non_final=True)

Constructs a new finite state machine with final output words for all states by implicitly reading trailing letters until a final state is reached.

INPUT:

  • letters – either an element of the input alphabet or a list of such elements. This is repeated cyclically when needed.
  • allow_non_final – a boolean (default: True) which indicates whether we allow that some states may be non-final in the resulting finite state machine. I.e., if False then each state has to have a path to a final state with input label matching letters.

OUTPUT:

A finite state machine.

The inplace version of this function is construct_final_word_out().

Suppose for the moment a single element letter as input for letters. This is equivalent to letters = [letter]. We will discuss the general case below.

Let word_in be a word over the input alphabet and assume that the original finite state machine transforms word_in to word_out reaching a possibly non-final state s. Let further \(k\) be the minimum number of letters letter such that there is a path from s to some final state f whose input label consists of \(k\) copies of letter and whose output label is path_word_out. Then the state s of the resulting finite state machine is a final state with final output path_word_out + f.final_word_out. Therefore, the new finite state machine transforms word_in to word_out + path_word_out + f.final_word_out.

This is e.g. useful for finite state machines operating on digit expansions: there, it is sometimes required to read a sufficient number of trailing zeros (at the most significant positions) in order to reach a final state and to flush all carries. In this case, this method constructs an essentially equivalent finite state machine in the sense that it not longer requires adding sufficiently many trailing zeros. However, it is the responsibility of the user to make sure that if adding trailing zeros to the input anyway, the output is equivalent.

If letters consists of more than one letter, then it is assumed that (not necessarily complete) cycles of letters are appended as trailing input.

EXAMPLES:

  1. A simple transducer transforming \(00\) blocks to \(01\) blocks:

    sage: T = Transducer([(0, 1, 0, 0), (1, 0, 0, 1)],
    ....:                initial_states=[0],
    ....:                final_states=[0])
    sage: T.process([0, 0, 0])
    (False, 1, [0, 1, 0])
    sage: T.process([0, 0, 0, 0])
    (True, 0, [0, 1, 0, 1])
    sage: F = T.with_final_word_out(0)
    sage: for f in F.iter_final_states():
    ....:     print f, f.final_word_out
    0 []
    1 [1]
    sage: F.process([0, 0, 0])
    (True, 1, [0, 1, 0, 1])
    sage: F.process([0, 0, 0, 0])
    (True, 0, [0, 1, 0, 1])
    
  2. A more realistic example: Addition of \(1\) in binary. We construct a transition function transforming the input to its binary expansion:

    sage: def binary_transition(carry, input):
    ....:     value = carry + input
    ....:     if value.mod(2) == 0:
    ....:         return (value/2, 0)
    ....:     else:
    ....:         return ((value-1)/2, 1)
    

    Now, we only have to start with a carry of \(1\) to get the required transducer:

    sage: T = Transducer(binary_transition,
    ....:                input_alphabet=[0, 1],
    ....:                initial_states=[1],
    ....:                final_states=[0])
    

    We test this for the binary expansion of \(7\):

    sage: T.process([1, 1, 1])
    (False, 1, [0, 0, 0])
    

    The final carry \(1\) has not be flushed yet, we have to add a trailing zero:

    sage: T.process([1, 1, 1, 0])
    (True, 0, [0, 0, 0, 1])
    

    We check that with this trailing zero, the transducer performs as advertised:

    sage: all(ZZ(T(k.bits()+[0]), base=2) == k + 1
    ....:     for k in srange(16))
    True
    

    However, most of the time, we produce superfluous trailing zeros:

    sage: T(11.bits()+[0])
    [0, 0, 1, 1, 0]
    

    We now use this method:

    sage: F = T.with_final_word_out(0)
    sage: for f in F.iter_final_states():
    ....:     print f, f.final_word_out
    1 [1]
    0 []
    

    The same tests as above, but we do not have to pad with trailing zeros anymore:

    sage: F.process([1, 1, 1])
    (True, 1, [0, 0, 0, 1])
    sage: all(ZZ(F(k.bits()), base=2) == k + 1
    ....:     for k in srange(16))
    True
    

    No more trailing zero in the output:

    sage: F(11.bits())
    [0, 0, 1, 1]
    sage: all(F(k.bits())[-1] == 1
    ....:     for k in srange(16))
    True
    
  3. Here is an example, where we allow trailing repeated \(10\):

    sage: T = Transducer([(0, 1, 0, 'a'),
    ....:                 (1, 2, 1, 'b'),
    ....:                 (2, 0, 0, 'c')],
    ....:                initial_states=[0],
    ....:                final_states=[0])
    sage: F = T.with_final_word_out([1, 0])
    sage: for f in F.iter_final_states():
    ....:     print f, ''.join(f.final_word_out)
    0
    1 bc
    

    Trying this with trailing repeated \(01\) does not produce a final_word_out for state 1, but for state 2:

    sage: F = T.with_final_word_out([0, 1])
    sage: for f in F.iter_final_states():
    ....:     print f, ''.join(f.final_word_out)
    0
    2 c
    
  4. Here another example with a more-letter trailing input:

    sage: T = Transducer([(0, 1, 0, 'a'),
    ....:                 (1, 2, 0, 'b'), (1, 2, 1, 'b'),
    ....:                 (2, 3, 0, 'c'), (2, 0, 1, 'e'),
    ....:                 (3, 1, 0, 'd'), (3, 1, 1, 'd')],
    ....:                initial_states=[0],
    ....:                final_states=[0],
    ....:                with_final_word_out=[0, 0, 1, 1])
    sage: for f in T.iter_final_states():
    ....:     print f, ''.join(f.final_word_out)
    0
    1 bcdbcdbe
    2 cdbe
    3 dbe
    

TESTS:

  1. Reading copies of letter may result in a cycle. In this simple example, we have no final state at all:

    sage: T = Transducer([(0, 1, 0, 0), (1, 0, 0, 0)],
    ....:                initial_states=[0])
    sage: T.with_final_word_out(0)
    Traceback (most recent call last):
    ...
    ValueError: The finite state machine contains
    a cycle starting at state 0 with input label 0
    and no final state.
    
  2. A unique transition with input word letter is required:

    sage: T = Transducer([(0, 1, 0, 0), (0, 2, 0, 0)])
    sage: T.with_final_word_out(0)
    Traceback (most recent call last):
    ...
    ValueError: No unique transition leaving state 0
    with input label 0.
    

    It is not a problem if there is no transition starting at state 1 with input word letter:

    sage: T = Transducer([(0, 1, 0, 0)])
    sage: F = T.with_final_word_out(0)
    sage: for f in F.iter_final_states():
    ....:     print f, f.final_word_out
    

    Anyhow, you can override this by:

    sage: T = Transducer([(0, 1, 0, 0)])
    sage: T.with_final_word_out(0, allow_non_final=False)
    Traceback (most recent call last):
    ...
    ValueError: No unique transition leaving state 1
    with input label 0.
    
  3. All transitions must have input labels of length \(1\):

    sage: T = Transducer([(0, 0, [], 0)])
    sage: T.with_final_word_out(0)
    Traceback (most recent call last):
    ...
    NotImplementedError: All transitions must have input
    labels of length 1. Consider calling split_transitions().
    sage: T = Transducer([(0, 0, [0, 1], 0)])
    sage: T.with_final_word_out(0)
    Traceback (most recent call last):
    ...
    NotImplementedError: All transitions must have input
    labels of length 1. Consider calling split_transitions().
    
  4. An empty list as input is not allowed:

    sage: T = Transducer([(0, 0, [], 0)])
    sage: T.with_final_word_out([])
    Traceback (most recent call last):
    ...
    ValueError: letters is not allowed to be an empty list.
    
class sage.combinat.finite_state_machine.Transducer(data=None, initial_states=None, final_states=None, input_alphabet=None, output_alphabet=None, determine_alphabets=None, with_final_word_out=None, store_states_dict=True, on_duplicate_transition=None)

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])
[1]
sage: T([1,1,0])
[0, 0, 1]
sage: ZZ(T(15.digits(base=2)+[0]), 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
cartesian_product(other, only_accessible_components=True)

Warning

The default output of this method is scheduled to change. This docstring describes the new default behaviour, which can already be achieved by setting FSMOldCodeTransducerCartesianProduct to False.

Return a new transducer which can simultaneously process an input with the machines self and other where the output labels are \(d\)-tuples of the original output labels.

INPUT:

  • other - a finite state machine (if \(d=2\)) or a list (or other iterable) of \(d-1\) finite state machines
  • only_accessible_components – If True (default), then the result is piped through accessible_components(). If no new_input_alphabet is given, it is determined by determine_alphabets().

OUTPUT:

A transducer which can simultaneously process an input with self and the machine(s) in other.

The set of states of the new transducer is the cartesian product of the set of states of self and other.

Let \((A_j, B_j, a_j, b_j)\) for \(j\in\{1, \ldots, d\}\) be transitions in the machines self and in other. Then there is a transition \(((A_1, \ldots, A_d), (B_1, \ldots, B_d), a, (b_1, \ldots, b_d))\) in the new transducer if \(a_1 = \cdots = a_d =: a\).

EXAMPLES:

Originally a different output was constructed by Transducer.cartesian_product(). This output is now produced by Transducer.intersection().

sage: transducer1 = Transducer([('A', 'A', 0, 0),
....:                           ('A', 'A', 1, 1)],
....:                          initial_states=['A'],
....:                          final_states=['A'],
....:                          determine_alphabets=True)
sage: transducer2 = Transducer([(0, 1, 0, ['b', 'c']),
....:                           (0, 0, 1, 'b'),
....:                           (1, 1, 0, 'a')],
....:                          initial_states=[0],
....:                          final_states=[1],
....:                          determine_alphabets=True)
sage: result = transducer1.cartesian_product(transducer2)
doctest:...: DeprecationWarning: The output of
Transducer.cartesian_product will change.
Please use Transducer.intersection for the original output.
See http://trac.sagemath.org/16061 for details.
sage: result
Transducer with 1 states

By setting FSMOldCodeTransducerCartesianProduct to False the new desired output is produced.

sage: sage.combinat.finite_state_machine.FSMOldCodeTransducerCartesianProduct = False
sage: result = transducer1.cartesian_product(transducer2)
sage: result
Transducer with 2 states
sage: result.transitions()
[Transition from ('A', 0) to ('A', 1): 0|(0, 'b'),(None, 'c'),
 Transition from ('A', 0) to ('A', 0): 1|(1, 'b'),
 Transition from ('A', 1) to ('A', 1): 0|(0, 'a')]
sage: result([1, 0, 0])
[(1, 'b'), (0, 'b'), (None, 'c'),  (0, 'a')]
sage: (transducer1([1, 0, 0]), transducer2([1, 0, 0]))
([1, 0, 0], ['b', 'b', 'c', 'a'])

Also final output words are correctly processed:

sage: transducer1.state('A').final_word_out = 2
sage: result = transducer1.cartesian_product(transducer2)
sage: result.final_states()[0].final_word_out
[(2, None)]

The following transducer counts the number of 11 blocks minus the number of 10 blocks over the alphabet [0, 1].

sage: count_11 = transducers.CountSubblockOccurrences(
....:     [1, 1],
....:     input_alphabet=[0, 1])
sage: count_10 = transducers.CountSubblockOccurrences(
....:     [1, 0],
....:     input_alphabet=[0, 1])
sage: count_11x10 = count_11.cartesian_product(count_10)
sage: difference = transducers.sub([0, 1])(count_11x10)
sage: T = difference.simplification().relabeled()
sage: T.initial_states()
[1]
sage: sorted(T.transitions())
[Transition from 0 to 1: 0|-1,
 Transition from 0 to 0: 1|1,
 Transition from 1 to 1: 0|0,
 Transition from 1 to 0: 1|0]
sage: input =  [0, 1, 1,  0, 1,  0, 0, 0, 1, 1, 1,  0]
sage: output = [0, 0, 1, -1, 0, -1, 0, 0, 0, 1, 1, -1]
sage: T(input) == output
True

If other is an automaton, then cartesian_product() returns self where the input is restricted to the input accepted by other.

For example, if the transducer transforms the standard binary expansion into the non-adjacent form and the automaton recognizes the binary expansion without adjacent ones, then the cartesian product of these two is a transducer which does not change the input (except for changing a to (a, None) and ignoring a leading \(0\)).

sage: NAF = Transducer([(0, 1, 0, None),
....:                   (0, 2, 1, None),
....:                   (1, 1, 0, 0),
....:                   (1, 2, 1, 0),
....:                   (2, 1, 0, 1),
....:                   (2, 3, 1, -1),
....:                   (3, 2, 0, 0),
....:                   (3, 3, 1, 0)],
....:                  initial_states=[0],
....:                  final_states=[1],
....:                  determine_alphabets=True)
sage: aut11 = Automaton([(0, 0, 0), (0, 1, 1), (1, 0, 0)],
....:                   initial_states=[0],
....:                   final_states=[0, 1],
....:                   determine_alphabets=True)
sage: res = NAF.cartesian_product(aut11)
sage: res([1, 0, 0, 1, 0, 1, 0])
[(1, None), (0, None), (0, None), (1, None), (0, None), (1, None)]

This is obvious because if the standard binary expansion does not have adjacent ones, then it is the same as the non-adjacent form.

Be aware that cartesian_product() is not commutative.

sage: aut11.cartesian_product(NAF)
Traceback (most recent call last):
...
TypeError: Only an automaton can be intersected with an automaton.

The cartesian product of more than two finite state machines can also be computed:

sage: T0 = transducers.CountSubblockOccurrences([0, 0], [0, 1, 2])
sage: T1 = transducers.CountSubblockOccurrences([1, 1], [0, 1, 2])
sage: T2 = transducers.CountSubblockOccurrences([2, 2], [0, 1, 2])
sage: T = T0.cartesian_product([T1, T2])
sage: T.transitions()
[Transition from ((), (), ()) to ((0,), (), ()): 0|(0, 0, 0),
 Transition from ((), (), ()) to ((), (1,), ()): 1|(0, 0, 0),
 Transition from ((), (), ()) to ((), (), (2,)): 2|(0, 0, 0),
 Transition from ((0,), (), ()) to ((0,), (), ()): 0|(1, 0, 0),
 Transition from ((0,), (), ()) to ((), (1,), ()): 1|(0, 0, 0),
 Transition from ((0,), (), ()) to ((), (), (2,)): 2|(0, 0, 0),
 Transition from ((), (1,), ()) to ((0,), (), ()): 0|(0, 0, 0),
 Transition from ((), (1,), ()) to ((), (1,), ()): 1|(0, 1, 0),
 Transition from ((), (1,), ()) to ((), (), (2,)): 2|(0, 0, 0),
 Transition from ((), (), (2,)) to ((0,), (), ()): 0|(0, 0, 0),
 Transition from ((), (), (2,)) to ((), (1,), ()): 1|(0, 0, 0),
 Transition from ((), (), (2,)) to ((), (), (2,)): 2|(0, 0, 1)]
sage: T([0, 0, 1, 1, 2, 2, 0, 1, 2, 2])
[(0, 0, 0),
 (1, 0, 0),
 (0, 0, 0),
 (0, 1, 0),
 (0, 0, 0),
 (0, 0, 1),
 (0, 0, 0),
 (0, 0, 0),
 (0, 0, 0),
 (0, 0, 1)]
intersection(other, only_accessible_components=True)

Returns a new transducer which accepts an input if it is accepted by both given finite state machines producing the same output.

INPUT:

OUTPUT:

A new transducer which computes the intersection (see below) of the languages of self and other.

The set of states of the transducer is the cartesian product of the set of states of both given transducer. There is a transition \(((A, B), (C, D), a, b)\) in the new transducer if there are transitions \((A, C, a, b)\) and \((B, D, a, b)\) in the old transducers.

EXAMPLES:

sage: transducer1 = Transducer([('1', '2', 1, 0),
....:                           ('2', '2', 1, 0),
....:                           ('2', '2', 0, 1)],
....:                          initial_states=['1'],
....:                          final_states=['2'])
sage: transducer2 = Transducer([('A', 'A', 1, 0),
....:                           ('A', 'B', 0, 0),
....:                           ('B', 'B', 0, 1),
....:                           ('B', 'A', 1, 1)],
....:                          initial_states=['A'],
....:                          final_states=['B'])
sage: res = transducer1.intersection(transducer2)
sage: res.transitions()
[Transition from ('1', 'A') to ('2', 'A'): 1|0,
 Transition from ('2', 'A') to ('2', 'A'): 1|0]

In general, transducers are not closed under intersection. But for transducer which do not have epsilon-transitions, the intersection is well defined (cf. [BaWo2012]). However, in the next example the intersection of the two transducers is not well defined. The intersection of the languages consists of \((a^n, b^n c^n)\). This set is not recognizable by a finite transducer.

sage: t1 = Transducer([(0, 0, 'a', 'b'),
....:                  (0, 1, None, 'c'),
....:                  (1, 1, None, 'c')],
....:                 initial_states=[0],
....:                 final_states=[0, 1])
sage: t2 = Transducer([('A', 'A', None, 'b'),
....:                  ('A', 'B', 'a', 'c'),
....:                  ('B', 'B', 'a', 'c')],
....:                 initial_states=['A'],
....:                 final_states=['A', 'B'])
sage: t2.intersection(t1)
Traceback (most recent call last):
...
ValueError: An epsilon-transition (with empty input or output)
was found.

TESTS:

sage: transducer1 = Transducer([('1', '2', 1, 0)],
....:                          initial_states=['1'],
....:                          final_states=['2'])
sage: transducer2 = Transducer([('A', 'B', 1, 0)],
....:                          initial_states=['A'],
....:                          final_states=['B'])
sage: res = transducer1.intersection(transducer2)
sage: res.final_states()
[('2', 'B')]
sage: transducer1.state('2').final_word_out = 1
sage: transducer2.state('B').final_word_out = 2
sage: res = transducer1.intersection(transducer2)
sage: res.final_states()
[]

REFERENCES:

[BaWo2012]Javier Baliosian and Dina Wonsever, Finite State Transducers, chapter in Handbook of Finite State Based Models and Applications, edited by Jiacun Wang, Chapman and Hall/CRC, 2012.
process(*args, **kwargs)

Warning

The default output of this method is scheduled to change. This docstring describes the new default behaviour, which can already be achieved by setting FSMOldProcessOutput to False.

Returns whether the transducer accepts the input, the state where the computation stops and which output is generated.

INPUT:

  • input_tape – the input tape can be a list or an iterable with entries from the input alphabet. If we are working with a multi-tape machine (see parameter use_multitape_input and notes below), then the tape is a list or tuple of tracks, each of which can be a list or an iterable with entries from the input alphabet.
  • initial_state or initial_states – the initial state(s) in which the machine starts. Either specify a single one with initial_state or a list of them with initial_states. If both are given, initial_state will be appended to initial_states. If neither is specified, the initial states of the finite state machine are taken.
  • list_of_outputs – (default: None) a boolean or None. If True, then the outputs are given in list form (even if we have no or only one single output). If False, then the result is never a list (an exception is raised if the result cannot be returned). If list_of_outputs=None the method determines automatically what to do (e.g. if a non-deterministic machine returns more than one path, then the output is returned in list form).
  • only_accepted – (default: False) a boolean. If set, then the first argument in the output is guaranteed to be True (if the output is a list, then the first argument of each element will be True).
  • full_output – (default: True) a boolean. If set, then the full output is given, otherwise only the generated output (the third entry below only). If the input is not accepted, a ValueError is raised.
  • always_include_output – if set (not by default), always include the output. This is inconsequential for a Transducer, but can be used in other classes derived from FiniteStateMachine where the output is suppressed by default, cf. Automaton.process().
  • format_output – a function that translates the written output (which is in form of a list) to something more readable. By default (None) identity is used here.
  • check_epsilon_transitions – (default: True) a boolean. If False, then epsilon transitions are not taken into consideration during process.
  • write_final_word_out – (default: True) a boolean specifying whether the final output words should be written or not.
  • use_multitape_input – (default: False) a boolean. If True, then the multi-tape mode of the process iterator is activated. See also the notes below for multi-tape machines.

OUTPUT:

The full output is a triple (or a list of triples, cf. parameter list_of_outputs), where

  • the first entry is True if the input string is accepted,
  • the second gives the reached state after processing the input tape (This is a state with label None if the input could not be processed, i.e., if at one point no transition to go on could be found.), and
  • the third gives a list of the output labels written during processing.

If full_output is False, then only the third entry is returned.

Note that in the case the transducer is not deterministic, all possible paths are taken into account.

By setting FSMOldProcessOutput to False the new desired output is produced.

This function uses an iterator which, in its simplest form, goes from one state to another in each step. To decide which way to go, it uses the input words of the outgoing transitions and compares them to the input tape. More precisely, in each step, the 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.

If the choice of the outgoing transition is not unique (i.e., we have a non-deterministic finite state machine), all possibilites are followed. This is done by splitting the process into several branches, one for each of the possible outgoing transitions.

The process (iteration) stops if all branches are finished, i.e., for no branch, there is any transition whose input word coincides with the processed input tape. This can simply happen when the entire tape was read.

Also see __call__() for a version of process() with shortened output.

Internally this function creates and works with an instance of FSMProcessIterator. This iterator can also be obtained with iter_process().

If working with multi-tape finite state machines, all input words of transitions are words of \(k\)-tuples of letters. Moreover, the input tape has to consist of \(k\) tracks, i.e., be a list or tuple of \(k\) iterators, one for each track.

Warning

Working with multi-tape finite state machines is still experimental and can lead to wrong outputs.

EXAMPLES:

sage: sage.combinat.finite_state_machine.FSMOldProcessOutput = False  # activate new output behavior
sage: binary_inverter = Transducer({'A': [('A', 0, 1), ('A', 1, 0)]},
....:                              initial_states=['A'], final_states=['A'])
sage: binary_inverter.process([0, 1, 0, 0, 1, 1])
(True, 'A', [1, 0, 1, 1, 0, 0])

If we are only interested in the output, we can also use:

sage: binary_inverter([0, 1, 0, 0, 1, 1])
[1, 0, 1, 1, 0, 0]

The following transducer transforms \(0^n 1\) to \(1^n 2\):

sage: T = Transducer([(0, 0, 0, 1), (0, 1, 1, 2)])
sage: T.state(0).is_initial = True
sage: T.state(1).is_final = True

We can see the different possibilites of the output by:

sage: [T.process(w) for w in [[1], [0, 1], [0, 0, 1], [0, 1, 1],
....:                         [0], [0, 0], [2, 0], [0, 1, 2]]]
[(True, 1, [2]), (True, 1, [1, 2]),
 (True, 1, [1, 1, 2]), (False, None, None),
 (False, 0, [1]), (False, 0, [1, 1]),
 (False, None, None), (False, None, None)]

If we just want a condensed output, we use:

sage: [T.process(w, full_output=False)
....:      for w in [[1], [0, 1], [0, 0, 1]]]
[[2], [1, 2], [1, 1, 2]]
sage: T.process([0], full_output=False)
Traceback (most recent call last):
...
ValueError: Invalid input sequence.
sage: T.process([0, 1, 2], full_output=False)
Traceback (most recent call last):
...
ValueError: Invalid input sequence.

It is equivalent to:

sage: [T(w) for w in [[1], [0, 1], [0, 0, 1]]]
[[2], [1, 2], [1, 1, 2]]
sage: T([0])
Traceback (most recent call last):
...
ValueError: Invalid input sequence.
sage: T([0, 1, 2])
Traceback (most recent call last):
...
ValueError: Invalid input sequence.

A cycle with empty input and empty output is correctly processed:

sage: T = Transducer([(0, 1, None, None), (1, 0, None, None)],
....:                initial_states=[0], final_states=[1])
sage: T.process([])
[(False, 0, []), (True, 1, [])]
sage: _ = T.add_transition(-1, 0, 0, 'r')
sage: T.state(-1).is_initial = True
sage: T.state(0).is_initial = False
sage: T.process([0])
[(False, 0, ['r']), (True, 1, ['r'])]

If there is a cycle with empty input but non-empty output, the possible outputs would be an infinite set:

sage: T = Transducer([(0, 1, None, 'z'), (1, 0, None, None)],
....:                initial_states=[0], final_states=[1])
sage: T.process([])
Traceback (most recent call last):
...
RuntimeError: State 0 is in an epsilon cycle (no input),
but output is written.

But if this cycle with empty input and non-empty output is not reached, the correct output is produced:

sage: _ = T.add_transition(-1, 0, 0, 'r')
sage: T.state(-1).is_initial = True
sage: T.state(0).is_initial = False
sage: T.process([])
(False, -1, [])
sage: T.process([0])
Traceback (most recent call last):
...
RuntimeError: State 0 is in an epsilon cycle (no input),
but output is written.

If we set check_epsilon_transitions=False, then no transitions with empty input are considered anymore. Thus cycles with empty input are no problem anymore:

sage: T.process([0], check_epsilon_transitions=False)
(False, 0, ['r'])

A simple example of a multi-tape transducer is the following: It writes the length of the first tape many letters a and then the length of the second tape many letters b:

sage: M = Transducer([(0, 0, (1, None), 'a'),
....:                 (0, 1, [], []),
....:                 (1, 1, (None, 1), 'b')],
....:                initial_states=[0],
....:                final_states=[1])
sage: M.process(([1, 1], [1]), use_multitape_input=True)
(True, 1, ['a', 'a', 'b'])

TESTS:

sage: T = Transducer([(0, 1, 1, 'a'), (1, 0, 1, 'b')],
....:                initial_states=[0, 1], final_states=[1])
sage: T.process([1, 1])
[(False, 0, ['a', 'b']), (True, 1, ['b', 'a'])]
sage: T.process([1, 1], T.state(0))
(False, 0, ['a', 'b'])
sage: T.state(1).final_word_out = 'c'
sage: T.process([1, 1], T.state(1))
(True, 1, ['b', 'a', 'c'])
sage: T.process([1, 1], T.state(1), write_final_word_out=False)
(True, 1, ['b', 'a'])

The parameter input_tape is required:

sage: T.process()
Traceback (most recent call last):
...
TypeError: No input tape given.
simplification()

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]
sage: fsm = Transducer([("A", "A", 0, 0),
....:                   ("A", "B", 1, 1),
....:                   ("A", "C", 1, -1),
....:                   ("B", "A", 2, 0),
....:                   ("C", "A", 2, 0)])
sage: fsm_simplified = fsm.simplification()
sage: fsm_simplified
Transducer with 2 states
sage: fsm_simplified.transitions()
[Transition from ('A',) to ('A',): 0|0,
 Transition from ('A',) to ('B', 'C'): 1|1,0,
 Transition from ('A',) to ('B', 'C'): 1|-1,0,
 Transition from ('B', 'C') to ('A',): 2|-]
sage: from sage.combinat.finite_state_machine import duplicate_transition_add_input
sage: T = Transducer([('A', 'A', 1/2, 0),
....:                 ('A', 'B', 1/4, 1),
....:                 ('A', 'C', 1/4, 1),
....:                 ('B', 'A', 1, 0),
....:                 ('C', 'A', 1, 0)],
....:                initial_states=[0],
....:                final_states=['A', 'B', 'C'],
....:                on_duplicate_transition=duplicate_transition_add_input)
sage: sorted(T.simplification().transitions())
[Transition from ('A',) to ('A',): 1/2|0,
 Transition from ('A',) to ('B', 'C'): 1/2|1,
 Transition from ('B', 'C') to ('A',): 1|0]

Illustrating the use of colors in order to avoid identification of states:

sage: T = Transducer( [[0,0,0,0], [0,1,1,1],
....:                  [1,0,0,0], [1,1,1,1]],
....:                 initial_states=[0],
....:                 final_states=[0,1])
sage: sorted(T.simplification().transitions())
[Transition from (0, 1) to (0, 1): 0|0,
 Transition from (0, 1) to (0, 1): 1|1]
sage: T.state(0).color = 0
sage: T.state(0).color = 1
sage: sorted(T.simplification().transitions())
[Transition from (0,) to (0,): 0|0,
 Transition from (0,) to (1,): 1|1,
 Transition from (1,) to (0,): 0|0,
 Transition from (1,) to (1,): 1|1]
sage.combinat.finite_state_machine.duplicate_transition_add_input(old_transition, new_transition)

Alternative function for handling duplicate transitions in finite state machines. This implementation adds the input label of the new transition to the input label of the old transition. This is intended for the case where a Markov chain is modelled by a finite state machine using the input labels as transition probabilities.

See the documentation of the on_duplicate_transition parameter of FiniteStateMachine.

INPUT:

  • old_transition – A transition in a finite state machine.
  • new_transition – A transition, identical to old_transition, which is to be inserted into the finite state machine.

OUTPUT:

A transition whose input weight is the sum of the input weights of old_transition and new_transition.

EXAMPLES:

sage: from sage.combinat.finite_state_machine import duplicate_transition_add_input
sage: from sage.combinat.finite_state_machine import FSMTransition
sage: duplicate_transition_add_input(FSMTransition('a', 'a', 1/2),
....:                                FSMTransition('a', 'a', 1/2))
Transition from 'a' to 'a': 1|-

Input labels must be lists of length 1:

sage: duplicate_transition_add_input(FSMTransition('a', 'a', [1, 1]),
....:                                FSMTransition('a', 'a', [1, 1]))
Traceback (most recent call last):
...
TypeError: Trying to use duplicate_transition_add_input on
"Transition from 'a' to 'a': 1,1|-" and
"Transition from 'a' to 'a': 1,1|-",
but input words are assumed to be lists of length 1
sage.combinat.finite_state_machine.duplicate_transition_ignore(old_transition, new_transition)

Default function for handling duplicate transitions in finite state machines. This implementation ignores the occurrence.

See the documentation of the on_duplicate_transition parameter of FiniteStateMachine.

INPUT:

  • old_transition – A transition in a finite state machine.
  • new_transition – A transition, identical to old_transition, which is to be inserted into the finite state machine.

OUTPUT:

The same transition, unchanged.

EXAMPLES:

sage: from sage.combinat.finite_state_machine import duplicate_transition_ignore
sage: from sage.combinat.finite_state_machine import FSMTransition
sage: duplicate_transition_ignore(FSMTransition(0, 0, 1),
....:                             FSMTransition(0, 0, 1))
Transition from 0 to 0: 1|-
sage.combinat.finite_state_machine.duplicate_transition_raise_error(old_transition, new_transition)

Alternative function for handling duplicate transitions in finite state machines. This implementation raises a ValueError.

See the documentation of the on_duplicate_transition parameter of FiniteStateMachine.

INPUT:

  • old_transition – A transition in a finite state machine.
  • new_transition – A transition, identical to old_transition, which is to be inserted into the finite state machine.

OUTPUT:

Nothing. A ValueError is raised.

EXAMPLES:

sage: from sage.combinat.finite_state_machine import duplicate_transition_raise_error
sage: from sage.combinat.finite_state_machine import FSMTransition
sage: duplicate_transition_raise_error(FSMTransition(0, 0, 1),
....:                                  FSMTransition(0, 0, 1))
Traceback (most recent call last):
...
ValueError: Attempting to re-insert transition Transition from 0 to 0: 1|-
sage.combinat.finite_state_machine.equal(iterator)

Checks whether all elements of iterator are equal.

INPUT:

  • iterator – an iterator of the elements to check

OUTPUT:

True or False.

This implements http://stackoverflow.com/a/3844832/1052778.

EXAMPLES:

sage: from sage.combinat.finite_state_machine import equal
sage: equal([0, 0, 0])
True
sage: equal([0, 1, 0])
False
sage: equal([])
True
sage: equal(iter([None, None]))
True

We can test other properties of the elements than the elements themselves. In the following example, we check whether all tuples have the same lengths:

sage: equal(len(x) for x in [(1, 2), (2, 3), (3, 1)])
True
sage: equal(len(x) for x in [(1, 2), (1, 2, 3), (3, 1)])
False
sage.combinat.finite_state_machine.full_group_by(l, key=<function <lambda> at 0x7f51a2678938>)

Group iterable l by values of key.

INPUT:

  • iterable l
  • key function key

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

  • that the keys are sortable (in contrast to the approach via sorted and itertools.groupby) and
  • that the keys are hashable (in contrast to the implementation proposed in http://stackoverflow.com/a/15250161).

However, it is required

  • that distinct keys have distinct str-representations.

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.

sage.combinat.finite_state_machine.is_Automaton(FSM)

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
sage.combinat.finite_state_machine.is_FSMProcessIterator(PI)

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([[0, 0, 0, 0]], initial_states=[0]), []))
True
sage.combinat.finite_state_machine.is_FSMState(S)

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
sage.combinat.finite_state_machine.is_FSMTransition(T)

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
sage.combinat.finite_state_machine.is_FiniteStateMachine(FSM)

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
sage.combinat.finite_state_machine.is_Transducer(FSM)

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
sage.combinat.finite_state_machine.setup_latex_preamble()

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.

See the section on LaTeX output in the introductory examples of this module.

TESTS:

sage: from sage.combinat.finite_state_machine import setup_latex_preamble
sage: setup_latex_preamble()
sage: ("\usepackage{tikz}" in latex.extra_preamble()) == latex.has_file("tikz.sty")
True
sage.combinat.finite_state_machine.startswith(list, prefix)

Determine whether list starts with the given prefix.

INPUT:

  • list – list
  • prefix – list representing the prefix

OUTPUT:

True or False.

Similar to str.startswith().

EXAMPLES:

sage: from sage.combinat.finite_state_machine import startswith
sage: startswith([1, 2, 3], [1, 2])
True
sage: startswith([1], [1, 2])
False
sage: startswith([1, 3, 2], [1, 2])
False
sage.combinat.finite_state_machine.tupleofwords_to_wordoftuples(tupleofwords)

Transposes a tuple of words over the alphabet to a word of tuples.

INPUT:

  • tupleofwords – a tuple of a list of letters.

OUTPUT:

A list of tuples.

Missing letters in the words are padded with the letter None (from the empty word).

EXAMPLES:

sage: from sage.combinat.finite_state_machine import (
....:     tupleofwords_to_wordoftuples)
sage: tupleofwords_to_wordoftuples(
....:     ([1, 2], [3, 4, 5, 6], [7]))
[(1, 3, 7), (2, 4, None), (None, 5, None), (None, 6, None)]
sage.combinat.finite_state_machine.wordoftuples_to_tupleofwords(wordoftuples)

Transposes a word of tuples to a tuple of words over the alphabet.

INPUT:

  • wordoftuples – a list of tuples of letters.

OUTPUT:

A tuple of lists.

Letters None (empty word) are removed from each word in the output.

EXAMPLES:

sage: from sage.combinat.finite_state_machine import (
....:     wordoftuples_to_tupleofwords)
sage: wordoftuples_to_tupleofwords(
....:     [(1, 2), (1, None), (1, None), (1, 2), (None, 2)])
([1, 1, 1, 1], [2, 2, 2])