automaton.multiply.ipynb

Kernel: Python 3

automaton.multiply(rhs, algo="auto")

This function is overloaded, it supports multiple different signatures:

• automaton.multiply(aut)

  The product (i.e., the concatenation) of two automata.

  Precondition:

  • In case of deterministic multiplication, the labelset of aut has to be free.

• automaton.multiply(num)

  The repeated multiplication (concatenation) of an automaton with itself. Exponent -1 denotes the infinity: the Kleene star.

• automaton.multiply((min, max))

  The sum of repeated multiplications of an automaton.

  Precondition:

  • min <= max

An algo parameter can be added to specify how the multiplication should be performed.

• automaton.multiply(aut,algo)

• automaton.multiply(num,algo)

• automaton.multiply((min, max),algo)

The algorithm has to be one of these:

• "auto": default parameter, same as "standard".

• "deterministic": produces a deterministic result.

• "general": introduces spontaneous transitions.

• "standard": does not introduce spontaneous transitions.

Preconditions:

• "deterministic": the labelset is free.

Postconditions:

• "deterministic": the result is a deterministic automaton.

• "standard": when applied to standard automata, the result is standard.

• "general": the context of the result automaton is nullable.

Caveats:

• "deterministic": the computation might not terminate on weighted automata. See automaton.determinize.

See also:

• expression.multiply

• polynomial.multiply

Examples

import vcsn
ctx = vcsn.context('lal_char, q')
def aut(e):
    return ctx.expression(e, 'none').standard()

Simple Multiplication

Instead of a.multiply(b), you may write a * b.

a = aut('<2>ab<3>'); a

b = aut('<5>cd<7>'); b

a * b

To force the execution of the general algorithm you can do it this way.

a.multiply(b, "general")

In order to satisfy any kind of input automaton, the general algorithm inserts a transition labelled by one, from each final transition of the left hand side automaton to each initial transition of the right hand side one.

a = vcsn.B.expression('a*+b').automaton(); a

The general algorithm introduces spontaneous transitions.

a.multiply(a, 'general')

When applied to standard automata, the standard multiplication yields a standard automaton.

a.multiply(a, 'standard')

The deterministic version returns a deterministic automaton.

a.multiply(a, 'deterministic')

Repeated Multiplication

Instead of a.multiply(3), you may write a ** 3. Beware that a * 3 actually denotes a.rweight(3).

aut('ab') ** 3

aut('a*') * 3

Use the exponent -1 to mean infinity. Alternatively, you may invoke a.star instead of a ** -1.

aut('ab') ** -1

aut('ab').star()

Sums of Repeated Multiplications

Instead of a.multiply((2, 4)), you may write a ** (2, 4). Again, use exponent -1 to mean infinity.

aut('ab') ** (2, 2)

aut('ab') ** (2, 4)

aut('ab') ** (2, -1)

aut('ab') ** (-1, 3)

aut('ab').multiply((-1, 3), "deterministic")

In some cases applying proper to the result automaton of the general algorithm will give you the result of the standard algorithm.

aut('ab').multiply((-1, 3), "general")

aut('ab').multiply((-1, 3), "general").proper()