Common Transducers (Finite State Machines Generators)¶
Transducers in Sage can be built through the transducers
object. It contains generators for common finite state machines. For example,
sage: I = transducers.Identity([0, 1, 2])
generates an identity transducer on the alphabet .
To construct transducers manually, you can use the class
Transducer
. See finite_state_machine
for more details and a lot of examples.
Transducers
Identity() |
Returns a transducer realizing the identity map. |
abs() |
Returns a transducer realizing absolute value. |
map() |
Returns a transducer realizing a function. |
operator() |
Returns a transducer realizing a binary operation. |
all() |
Returns a transducer realizing logical and . |
any() |
Returns a transducer realizing logical or . |
add() |
Returns a transducer realizing addition. |
sub() |
Returns a transducer realizing subtraction. |
CountSubblockOccurrences() |
Returns a transducer counting the occurrences of a subblock. |
Wait() |
Returns a transducer writing False until first (or k-th) true input is read. |
weight() |
Returns a transducer realizing the Hamming weight. |
GrayCode() |
Returns a transducer realizing binary Gray code. |
Recursion() |
Returns a transducer defined by recursions. |
AUTHORS:
- Clemens Heuberger (2014-04-07): initial version
- Sara Kropf (2014-04-10): some changes in TransducerGenerator
- Daniel Krenn (2014-04-15): improved common docstring during review
- Clemens Heuberger, Daniel Krenn, Sara Kropf (2014-04-16–2014-05-02): A couple of improvements. Details see trac ticket #16141, trac ticket #16142, trac ticket #16143, trac ticket #16186.
- Sara Kropf (2014-04-29): weight transducer
- Clemens Heuberger, Daniel Krenn (2014-07-18): transducers Wait, all, any
- Clemens Heuberger (2014-08-10): transducer Recursion
ACKNOWLEDGEMENT:
- Clemens Heuberger, Daniel Krenn and Sara Kropf are supported by the Austrian Science Fund (FWF): P 24644-N26.
Functions and methods¶
-
class
sage.combinat.finite_state_machine_generators.
TransducerGenerators
¶ Bases:
object
A class consisting of constructors for several common transducers.
A list of all transducers in this database is available via tab completion. Type “
transducers.
” and then hit tab to see which transducers are available.The transducers currently in this class include:
-
CountSubblockOccurrences
(block, input_alphabet)¶ Returns a transducer counting the number of (possibly overlapping) occurrences of a block in the input.
INPUT:
block
– a list (or other iterable) of letters.input_alphabet
– a list or other iterable.
OUTPUT:
A transducer counting (in unary) the number of occurrences of the given block in the input. Overlapping occurrences are counted several times.
Denoting the block by
, the input word by
and the output word by
, we have
if and only if
. Otherwise,
.
EXAMPLES:
Counting the number of
10
blocks over the alphabet[0, 1]
:sage: T = transducers.CountSubblockOccurrences( ....: [1, 0], ....: [0, 1]) sage: sorted(T.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: T.input_alphabet [0, 1] sage: T.output_alphabet [0, 1] sage: T.initial_states() [()] sage: T.final_states() [(), (1,)]
Check some sequence:
sage: sage.combinat.finite_state_machine.FSMOldProcessOutput = False sage: T([0, 1, 0, 1, 1, 0]) [0, 0, 1, 0, 0, 1]
Counting the number of
11
blocks over the alphabet[0, 1]
:sage: T = transducers.CountSubblockOccurrences( ....: [1, 1], ....: [0, 1]) sage: sorted(T.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]
Check some sequence:
sage: sage.combinat.finite_state_machine.FSMOldProcessOutput = False sage: T([0, 1, 0, 1, 1, 0]) [0, 0, 0, 0, 1, 0]
Counting the number of
1010
blocks over the alphabet[0, 1, 2]
:sage: T = transducers.CountSubblockOccurrences( ....: [1, 0, 1, 0], ....: [0, 1, 2]) sage: sorted(T.transitions()) [Transition from () to (): 0|0, Transition from () to (1,): 1|0, Transition from () to (): 2|0, Transition from (1,) to (1, 0): 0|0, Transition from (1,) to (1,): 1|0, Transition from (1,) to (): 2|0, Transition from (1, 0) to (): 0|0, Transition from (1, 0) to (1, 0, 1): 1|0, Transition from (1, 0) to (): 2|0, Transition from (1, 0, 1) to (1, 0): 0|1, Transition from (1, 0, 1) to (1,): 1|0, Transition from (1, 0, 1) to (): 2|0] sage: input = [0, 1, 0, 1, 0, 1, 0, 0, 1, 0, 1, 0, 2] sage: output = [0, 0, 0, 0, 1, 0, 1, 0, 0, 0, 0, 1, 0] sage: sage.combinat.finite_state_machine.FSMOldProcessOutput = False sage: T(input) == output True
-
GrayCode
()¶ Returns a transducer converting the standard binary expansion to Gray code.
INPUT:
Nothing.
OUTPUT:
A transducer.
Cf. the Wikipedia article Gray_code for a description of the Gray code.
EXAMPLE:
sage: G = transducers.GrayCode() sage: G Transducer with 3 states sage: sage.combinat.finite_state_machine.FSMOldProcessOutput = False sage: for v in srange(0, 10): ....: print v, G(v.digits(base=2)) 0 [] 1 [1] 2 [1, 1] 3 [0, 1] 4 [0, 1, 1] 5 [1, 1, 1] 6 [1, 0, 1] 7 [0, 0, 1] 8 [0, 0, 1, 1] 9 [1, 0, 1, 1]
In the example Gray Code in the documentation of the
finite_state_machine
module, the Gray code transducer is derived from the algorithm converting the binary expansion to the Gray code. The result is the same as the one given here.
-
Identity
(input_alphabet)¶ Returns the identity transducer realizing the identity map.
INPUT:
input_alphabet
– a list or other iterable.
OUTPUT:
A transducer mapping each word over
input_alphabet
to itself.EXAMPLES:
sage: T = transducers.Identity([0, 1]) sage: sorted(T.transitions()) [Transition from 0 to 0: 0|0, Transition from 0 to 0: 1|1] sage: T.initial_states() [0] sage: T.final_states() [0] sage: T.input_alphabet [0, 1] sage: T.output_alphabet [0, 1] sage: sage.combinat.finite_state_machine.FSMOldProcessOutput = False sage: T([0, 1, 0, 1, 1]) [0, 1, 0, 1, 1]
-
Recursion
(recursions, base, function=None, var=None, input_alphabet=None, word_function=None, is_zero=None, output_rings=[Integer Ring, Rational Field])¶ Return a transducer realizing the given recursion when reading the digit expansion with base
base
.INPUT:
recursions
– list or iterable of equations. Each equation has either the formf(base^K * n + r) == f(base^k * n + s) + t
for some integers0 <= k < K
,r
and somet
—valid for alln
such that the arguments on both sides are non-negative—
or the form
f(r) == t
for some integerr
and somet
.
Alternatively, an equation may be replaced by a
transducers.RecursionRule
with the attributesK
,r
,k
,s
,t
as above or a tuple(r, t)
. Note thatt
must be a list in this case.base
– base of the digit expansion.function
– symbolic functionf
occuring in the recursions.var
– symbolic variable.input_alphabet
– (default:None
) a list of digits to be used as the input alphabet. IfNone
and the base is an integer,input_alphabet
is chosen to besrange(base.abs())
.word_function
– (default:None
) a symbolic function. If notNone
,word_function(arg1, ..., argn)
in a symbolic recurrence relation is interpreted as a transition with output[arg1, ..., argn]
. This could not be entered in a symbolic recurrence relation because lists do not coerce into theSymbolicRing
.is_zero
– (default:None
) a callable. The recursion relations are only well-posed if there is no cycle with non-zero output and input consisting of zeros. This parameter is used to determine whether the output of such a cycle is non-zero. By default, the output must evaluate toFalse
as a boolean.output_rings
– (default:[ZZ, QQ]
) a list of rings. The output labels are converted into the first ring of the list in which they are contained. If they are not contained in any ring, they remain in whatever ring they are after parsing the recursions, typically the symbolic ring.
OUTPUT:
A transducer
T
.The transducer is constructed such that
T(expansion) == f(n)
ifexpansion
is the digit expansion ofn
to the basebase
with the given input alphabet as set of digits. Here, the+
on the right hand side of the recurrence relation is interpreted as the concatenation of words.The formal equations and initial conditions in the recursion have to be selected such that
f
is uniquely defined.EXAMPLES:
The following example computes the Hamming weight of the ternary expansion of integers.
sage: function('f') f sage: var('n') n sage: T = transducers.Recursion([ ....: f(3*n + 1) == f(n) + 1, ....: f(3*n + 2) == f(n) + 1, ....: f(3*n) == f(n), ....: f(0) == 0], ....: 3, f, n) sage: T.transitions() [Transition from (0, 0) to (0, 0): 0|-, Transition from (0, 0) to (0, 0): 1|1, Transition from (0, 0) to (0, 0): 2|1]
To illustrate what this transducer does, we consider the example of
:
sage: ternary_expansion = 601.digits(base=3) sage: ternary_expansion [1, 2, 0, 1, 1, 2] sage: weight_sequence = T(ternary_expansion) sage: weight_sequence [1, 1, 1, 1, 1] sage: sum(weight_sequence) 5
Note that the digit zero does not show up in the output because the equation
f(3*n) == f(n)
means that no output is added tof(n)
.The following example computes the Hamming weight of the non-adjacent form, cf. the Wikipedia article Non-adjacent_form.
sage: function('f') f sage: var('n') n sage: T = transducers.Recursion([ ....: f(4*n + 1) == f(n) + 1, ....: f(4*n - 1) == f(n) + 1, ....: f(2*n) == f(n), ....: f(0) == 0], ....: 2, f, n) sage: T.transitions() [Transition from (0, 0) to (0, 0): 0|-, Transition from (0, 0) to (1, 1): 1|-, Transition from (1, 1) to (0, 0): 0|1, Transition from (1, 1) to (1, 0): 1|1, Transition from (1, 0) to (1, 1): 0|-, Transition from (1, 0) to (1, 0): 1|-] sage: [(s.label(), s.final_word_out) ....: for s in T.iter_final_states()] [((0, 0), []), ((1, 1), [1]), ((1, 0), [1])]
As we are interested in the weight only, we also output
for numbers congruent to
mod
. The actual expansion is computed in the next example.
Consider the example of
(as usual, the digit
is denoted by
and digits are written from the most significant digit at the left to the least significant digit at the right; for the transducer, we have to give the digits in the reverse order):
sage: NAF = [1, 0, -1, 0, 0, 1] sage: ZZ(NAF, base=2) 29 sage: binary_expansion = 29.digits(base=2) sage: binary_expansion [1, 0, 1, 1, 1] sage: T(binary_expansion) [1, 1, 1] sage: sum(T(binary_expansion)) 3
Indeed, the given non-adjacent form has three non-zero digits.
The following example computes the non-adjacent form from the binary expansion, cf. the Wikipedia article Non-adjacent_form. In contrast to the previous example, we actually compute the expansion, not only the weight.
We have to write the output
when converting an even number. This cannot be encoded directly by an equation in the symbolic ring, because
f(2*n) == f(n) + 0
would be equivalent tof(2*n) == f(n)
and an empty output would be written. Therefore, we wrap the output in the symbolic functionw
and use the parameterword_function
to announce this.Similarly, we use
w(-1, 0)
to write an output word of lengthin one interation. Finally, we write
f(0) == w()
to write an empty word upon completion.Moreover, there is a cycle with output
[0]
which—from the point of view of this method—is a contradicting recursion. We override this by the parameteris_zero
.sage: var('n') n sage: function('f w') (f, w) sage: T = transducers.Recursion([ ....: f(2*n) == f(n) + w(0), ....: f(4*n + 1) == f(n) + w(1, 0), ....: f(4*n - 1) == f(n) + w(-1, 0), ....: f(0) == w()], ....: 2, f, n, ....: word_function=w, ....: is_zero=lambda x: sum(x).is_zero()) sage: T.transitions() [Transition from (0, 0) to (0, 0): 0|0, Transition from (0, 0) to (1, 1): 1|-, Transition from (1, 1) to (0, 0): 0|1,0, Transition from (1, 1) to (1, 0): 1|-1,0, Transition from (1, 0) to (1, 1): 0|-, Transition from (1, 0) to (1, 0): 1|0] sage: for s in T.iter_states(): ....: print s, s.final_word_out (0, 0) [] (1, 1) [1, 0] (1, 0) [1, 0]
We again consider the example of
:
sage: T(29.digits(base=2)) [1, 0, -1, 0, 0, 1, 0]
The same transducer can also be entered bypassing the symbolic equations:
sage: R = transducers.RecursionRule sage: TR = transducers.Recursion([ ....: R(K=1, r=0, k=0, s=0, t=[0]), ....: R(K=2, r=1, k=0, s=0, t=[1, 0]), ....: R(K=2, r=-1, k=0, s=0, t=[-1, 0]), ....: (0, [])], ....: 2, ....: is_zero=lambda x: sum(x).is_zero()) sage: TR == T True
Here is an artificial example where some of the
are negative:
sage: function('f') f sage: var('n') n sage: T = transducers.Recursion([ ....: f(2*n + 1) == f(n-1) + 1, ....: f(2*n) == f(n), ....: f(1) == 1, ....: f(0) == 0], 2, f, n) sage: T.transitions() [Transition from (0, 0) to (0, 0): 0|-, Transition from (0, 0) to (1, 1): 1|-, Transition from (1, 1) to (-1, 1): 0|1, Transition from (1, 1) to (0, 0): 1|1, Transition from (-1, 1) to (-1, 2): 0|-, Transition from (-1, 1) to (1, 2): 1|-, Transition from (-1, 2) to (-1, 1): 0|1, Transition from (-1, 2) to (0, 0): 1|1, Transition from (1, 2) to (-1, 2): 0|1, Transition from (1, 2) to (1, 2): 1|1] sage: [(s.label(), s.final_word_out) ....: for s in T.iter_final_states()] [((0, 0), []), ((1, 1), [1]), ((-1, 1), [0]), ((-1, 2), [0]), ((1, 2), [1])]
Abelian complexity of the paperfolding sequence (cf. [HKP2015], Example 2.8):
sage: T = transducers.Recursion([ ....: f(4*n) == f(2*n), ....: f(4*n+2) == f(2*n+1)+1, ....: f(16*n+1) == f(8*n+1), ....: f(16*n+5) == f(4*n+1)+2, ....: f(16*n+11) == f(4*n+3)+2, ....: f(16*n+15) == f(2*n+2)+1, ....: f(1) == 2, f(0) == 0] ....: + [f(16*n+jj) == f(2*n+1)+2 for jj in [3,7,9,13]], ....: 2, f, n) sage: T.transitions() [Transition from (0, 0) to (0, 1): 0|-, Transition from (0, 0) to (1, 1): 1|-, Transition from (0, 1) to (0, 1): 0|-, Transition from (0, 1) to (1, 1): 1|1, Transition from (1, 1) to (1, 2): 0|-, Transition from (1, 1) to (3, 2): 1|-, Transition from (1, 2) to (1, 3): 0|-, Transition from (1, 2) to (5, 3): 1|-, Transition from (3, 2) to (3, 3): 0|-, Transition from (3, 2) to (7, 3): 1|-, Transition from (1, 3) to (1, 3): 0|-, Transition from (1, 3) to (1, 1): 1|2, Transition from (5, 3) to (1, 2): 0|2, Transition from (5, 3) to (1, 1): 1|2, Transition from (3, 3) to (1, 1): 0|2, Transition from (3, 3) to (3, 2): 1|2, Transition from (7, 3) to (1, 1): 0|2, Transition from (7, 3) to (2, 1): 1|1, Transition from (2, 1) to (1, 1): 0|1, Transition from (2, 1) to (2, 1): 1|-] sage: for s in T.iter_states(): ....: print s, s.final_word_out (0, 0) [] (0, 1) [] (1, 1) [2] (1, 2) [2] (3, 2) [2, 2] (1, 3) [2] (5, 3) [2, 2] (3, 3) [2, 2] (7, 3) [2, 2] (2, 1) [1, 2] sage: list(sum(T(n.bits())) for n in srange(1, 21)) [2, 3, 4, 3, 4, 5, 4, 3, 4, 5, 6, 5, 4, 5, 4, 3, 4, 5, 6, 5]
We now demonstrate the use of the
output_rings
parameter. If nooutput_rings
are specified, the output labels are converted intoZZ
:sage: function('f') f sage: var('n') n sage: T = transducers.Recursion([ ....: f(2*n + 1) == f(n) + 1, ....: f(2*n) == f(n), ....: f(0) == 2], ....: 2, f, n) sage: for t in T.transitions(): ....: print [x.parent() for x in t.word_out] [] [Integer Ring] sage: [x.parent() for x in T.states()[0].final_word_out] [Integer Ring]
In contrast, if
output_rings
is set to the empty list, the results are not converted:sage: T = transducers.Recursion([ ....: f(2*n + 1) == f(n) + 1, ....: f(2*n) == f(n), ....: f(0) == 2], ....: 2, f, n, output_rings=[]) sage: for t in T.transitions(): ....: print [x.parent() for x in t.word_out] [] [Symbolic Ring] sage: [x.parent() for x in T.states()[0].final_word_out] [Symbolic Ring]
Finally, we use a somewhat questionable conversion:
sage: T = transducers.Recursion([ ....: f(2*n + 1) == f(n) + 1, ....: f(2*n) == f(n), ....: f(0) == 0], ....: 2, f, n, output_rings=[GF(5)]) sage: for t in T.transitions(): ....: print [x.parent() for x in t.word_out] [] [Finite Field of size 5]
Todo
Extend the method to
- non-integral bases,
- higher dimensions.
ALGORITHM:
See [HKP2015], Section 6. However, there are also recursion transitions for states of level
if the recursion rules allow such a transition. Furthermore, the intermediate step of a non-deterministic transducer is left out by implicitly using recursion transitions. The well-posedness is checked in a truncated version of the recursion digraph.
TESTS:
The following tests fail due to missing or superfluous recursions or initial conditions.
sage: var('n') n sage: function('f') f sage: transducers.Recursion([f(2*n) == f(n)], ....: 2, f, n) Traceback (most recent call last): ... ValueError: Missing recursions for input congruent to [1] modulo 2.
sage: transducers.Recursion([f(2*n + 1) == f(n), ....: f(4*n) == f(2*n) + 1, ....: f(2*n) == f(n) +1], ....: 2, f, n) Traceback (most recent call last): ... ValueError: Conflicting rules congruent to 0 modulo 4.
sage: transducers.Recursion([f(2*n + 1) == f(n) + 1, ....: f(2*n) == f(n), ....: f(0) == 0, ....: f(42) == 42], 2, f, n) Traceback (most recent call last): ... ValueError: Superfluous initial values for [42].
sage: transducers.Recursion([f(2*n + 1) == f(n) + 1, ....: f(2*n) == f(n - 2) + 4, ....: f(0) == 0], 2, f, n) Traceback (most recent call last): ... ValueError: Missing initial values for [2].
Here is an example of a transducer with a conflicting rule (it cannot hold for
):
sage: T = transducers.Recursion([ ....: f(2*n + 1) == f(n - 1), ....: f(2*n) == f(n) + 1, ....: f(1) == 1, ....: f(0) == 0], 2, f, n) Traceback (most recent call last): ... ValueError: Conflicting recursion for [0].
-
class
RecursionRule
¶ Bases:
tuple
-
K
¶ Alias for field number 0
-
k
¶ Alias for field number 2
-
r
¶ Alias for field number 1
-
s
¶ Alias for field number 3
-
t
¶ Alias for field number 4
-
-
TransducerGenerators.
Wait
(input_alphabet, threshold=1)¶ Writes
False
until reading thethreshold
-th occurrence of a true input letter; then writesTrue
.INPUT:
input_alphabet
– a list or other iterable.threshold
– a positive integer specifying how many occurrences ofTrue
inputs are waited for.
OUTPUT:
A transducer writing
False
until thethreshold
-th true (Python’s standard conversion to boolean is used to convert the actual input to boolean) input is read. Subsequently, the transducer writesTrue
.EXAMPLES:
sage: T = transducers.Wait([0, 1]) sage: T([0, 0, 1, 0, 1, 0]) [False, False, True, True, True, True] sage: T2 = transducers.Wait([0, 1], threshold=2) sage: T2([0, 0, 1, 0, 1, 0]) [False, False, False, False, True, True]
-
TransducerGenerators.
abs
(input_alphabet)¶ Returns a transducer which realizes the letter-wise absolute value of an input word over the given input alphabet.
INPUT:
input_alphabet
– a list or other iterable.
OUTPUT:
A transducer mapping
to
.
EXAMPLE:
The following transducer realizes letter-wise absolute value:
sage: T = transducers.abs([-1, 0, 1]) sage: T.transitions() [Transition from 0 to 0: -1|1, Transition from 0 to 0: 0|0, Transition from 0 to 0: 1|1] sage: T.initial_states() [0] sage: T.final_states() [0] sage: T([-1, -1, 0, 1]) [1, 1, 0, 1]
-
TransducerGenerators.
add
(input_alphabet, number_of_operands=2)¶ Returns a transducer which realizes addition on pairs over the given input alphabet.
INPUT:
input_alphabet
– a list or other iterable.number_of_operands
– (default:) it specifies the number of input arguments the operator takes.
OUTPUT:
A transducer mapping an input word
to the word
.
The input alphabet of the generated transducer is the cartesian product of
number_of_operands
copies ofinput_alphabet
.EXAMPLE:
The following transducer realizes letter-wise addition:
sage: T = transducers.add([0, 1]) sage: T.transitions() [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)|2] sage: T.input_alphabet [(0, 0), (0, 1), (1, 0), (1, 1)] sage: T.initial_states() [0] sage: T.final_states() [0] sage: T([(0, 0), (0, 1), (1, 0), (1, 1)]) [0, 1, 1, 2]
More than two operands can also be handled:
sage: T3 = transducers.add([0, 1], number_of_operands=3) sage: T3.input_alphabet [(0, 0, 0), (0, 0, 1), (0, 1, 0), (0, 1, 1), (1, 0, 0), (1, 0, 1), (1, 1, 0), (1, 1, 1)] sage: T3([(0, 0, 0), (0, 1, 0), (0, 1, 1), (1, 1, 1)]) [0, 1, 2, 3]
-
TransducerGenerators.
all
(input_alphabet, number_of_operands=2)¶ Returns a transducer which realizes logical
and
over the given input alphabet.INPUT:
input_alphabet
– a list or other iterable.number_of_operands
– (default:) specifies the number of input arguments for the
and
operation.
OUTPUT:
A transducer mapping an input word
to the word
.
The input alphabet of the generated transducer is the cartesian product of
number_of_operands
copies ofinput_alphabet
.EXAMPLE:
The following transducer realizes letter-wise logical
and
:sage: T = transducers.all([False, True]) sage: T.transitions() [Transition from 0 to 0: (False, False)|False, Transition from 0 to 0: (False, True)|False, Transition from 0 to 0: (True, False)|False, Transition from 0 to 0: (True, True)|True] sage: T.input_alphabet [(False, False), (False, True), (True, False), (True, True)] sage: T.initial_states() [0] sage: T.final_states() [0] sage: T([(False, False), (False, True), (True, False), (True, True)]) [False, False, False, True]
More than two operands and other input alphabets (with conversion to boolean) are also possible:
sage: T3 = transducers.all([0, 1], number_of_operands=3) sage: T3([(0, 0, 0), (1, 0, 0), (1, 1, 1)]) [False, False, True]
-
TransducerGenerators.
any
(input_alphabet, number_of_operands=2)¶ Returns a transducer which realizes logical
or
over the given input alphabet.INPUT:
input_alphabet
– a list or other iterable.number_of_operands
– (default:) specifies the number of input arguments for the
or
operation.
OUTPUT:
A transducer mapping an input word
to the word
.
The input alphabet of the generated transducer is the cartesian product of
number_of_operands
copies ofinput_alphabet
.EXAMPLE:
The following transducer realizes letter-wise logical
or
:sage: T = transducers.any([False, True]) sage: T.transitions() [Transition from 0 to 0: (False, False)|False, Transition from 0 to 0: (False, True)|True, Transition from 0 to 0: (True, False)|True, Transition from 0 to 0: (True, True)|True] sage: T.input_alphabet [(False, False), (False, True), (True, False), (True, True)] sage: T.initial_states() [0] sage: T.final_states() [0] sage: T([(False, False), (False, True), (True, False), (True, True)]) [False, True, True, True]
More than two operands and other input alphabets (with conversion to boolean) are also possible:
sage: T3 = transducers.any([0, 1], number_of_operands=3) sage: T3([(0, 0, 0), (1, 0, 0), (1, 1, 1)]) [False, True, True]
-
TransducerGenerators.
map
(f, input_alphabet)¶ Return a transducer which realizes a function on the alphabet.
INPUT:
f
– function to realize.input_alphabet
– a list or other iterable.
OUTPUT:
A transducer mapping an input letter
to
.
EXAMPLE:
The following binary transducer realizes component-wise absolute value (this transducer is also available as
abs()
):sage: T = transducers.map(abs, [-1, 0, 1]) sage: T.transitions() [Transition from 0 to 0: -1|1, Transition from 0 to 0: 0|0, Transition from 0 to 0: 1|1] sage: T.input_alphabet [-1, 0, 1] sage: T.initial_states() [0] sage: T.final_states() [0] sage: T([-1, 1, 0, 1]) [1, 1, 0, 1]
See also
-
TransducerGenerators.
operator
(operator, input_alphabet, number_of_operands=2)¶ Returns a transducer which realizes an operation on tuples over the given input alphabet.
INPUT:
operator
– operator to realize. It is a function which takesnumber_of_operands
input arguments (each out ofinput_alphabet
).input_alphabet
– a list or other iterable.number_of_operands
– (default:) it specifies the number of input arguments the operator takes.
OUTPUT:
A transducer mapping an input letter
to
. Here,
equals
number_of_operands
.The input alphabet of the generated transducer is the cartesian product of
number_of_operands
copies ofinput_alphabet
.EXAMPLE:
The following binary transducer realizes component-wise addition (this transducer is also available as
add()
):sage: import operator sage: T = transducers.operator(operator.add, [0, 1]) sage: T.transitions() [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)|2] sage: T.input_alphabet [(0, 0), (0, 1), (1, 0), (1, 1)] sage: T.initial_states() [0] sage: T.final_states() [0] sage: T([(0, 0), (0, 1), (1, 0), (1, 1)]) [0, 1, 1, 2]
Note that for a unary operator the input letters of the new transducer are tuples of length
:
sage: T = transducers.operator(abs, ....: [-1, 0, 1], ....: number_of_operands=1) sage: T([-1, 1, 0]) Traceback (most recent call last): ... ValueError: Invalid input sequence. sage: T([(-1,), (1,), (0,)]) [1, 1, 0]
Compare this with the transducer generated by
map()
:sage: T = transducers.map(abs, ....: [-1, 0, 1]) sage: T([-1, 1, 0]) [1, 1, 0]
In fact, this transducer is also available as
abs()
:sage: T = transducers.abs([-1, 0, 1]) sage: T([-1, 1, 0]) [1, 1, 0]
-
TransducerGenerators.
sub
(input_alphabet)¶ Returns a transducer which realizes subtraction on pairs over the given input alphabet.
INPUT:
input_alphabet
– a list or other iterable.
OUTPUT:
A transducer mapping an input word
to the word
.
The input alphabet of the generated transducer is the cartesian product of two copies of
input_alphabet
.EXAMPLE:
The following transducer realizes letter-wise subtraction:
sage: T = transducers.sub([0, 1]) sage: T.transitions() [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: T.input_alphabet [(0, 0), (0, 1), (1, 0), (1, 1)] sage: T.initial_states() [0] sage: T.final_states() [0] sage: T([(0, 0), (0, 1), (1, 0), (1, 1)]) [0, -1, 1, 0]
-
TransducerGenerators.
weight
(input_alphabet, zero=0)¶ Returns a transducer which realizes the Hamming weight of the input over the given input alphabet.
INPUT:
input_alphabet
– a list or other iterable.zero
– the zero symbol in the alphabet used
OUTPUT:
A transducer mapping
to
.
The Hamming weight is defined as the number of non-zero digits in the input sequence over the alphabet
input_alphabet
(see Wikipedia article Hamming_weight). The output sequence of the transducer is a unary encoding of the Hamming weight. Thus the sum of the output sequence is the Hamming weight of the input.EXAMPLES:
sage: W = transducers.weight([-1, 0, 2]) sage: W.transitions() [Transition from 0 to 0: -1|1, Transition from 0 to 0: 0|0, Transition from 0 to 0: 2|1] sage: unary_weight = W([-1, 0, 0, 2, -1]) sage: unary_weight [1, 0, 0, 1, 1] sage: weight = add(unary_weight) sage: weight 3
Also the joint Hamming weight can be computed:
sage: v1 = vector([-1, 0]) sage: v0 = vector([0, 0]) sage: W = transducers.weight([v1, v0]) sage: unary_weight = W([v1, v0, v1, v0]) sage: add(unary_weight) 2
For the input alphabet
[-1, 0, 1]
the weight transducer is the same as the absolute value transducerabs()
:sage: W = transducers.weight([-1, 0, 1]) sage: A = transducers.abs([-1, 0, 1]) sage: W == A True
For other input alphabets, we can specify the zero symbol:
sage: W = transducers.weight(['a', 'b'], zero='a') sage: add(W(['a', 'b', 'b'])) 2
-