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:

See also:

Examples

In [1]:
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.

In [2]:
a = aut('<2>ab<3>'); a
Out[2]:
%3 I0 0 0 I0->0 F3 1 1 0->1 ⟨2⟩a 3 3 1->3 b 3->F3 ⟨3⟩
In [3]:
b = aut('<5>cd<7>'); b
Out[3]:
%3 I0 0 0 I0->0 F3 1 1 0->1 ⟨5⟩c 3 3 1->3 d 3->F3 ⟨7⟩
In [4]:
a * b
Out[4]:
%3 I0 0 0 I0->0 F4 1 1 0->1 ⟨2⟩a 2 2 1->2 b 3 3 2->3 ⟨15⟩c 4 4 3->4 d 4->F4 ⟨7⟩

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

In [5]:
a.multiply(b, "general")
Out[5]:
%3 I0 0 0 I0->0 F5 1 1 0->1 ⟨2⟩a 2 2 1->2 b 3 3 2->3 ⟨3⟩ε 4 4 3->4 ⟨5⟩c 5 5 4->5 d 5->F5 ⟨7⟩

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.

In [6]:
a = vcsn.B.expression('a*+b').automaton(); a
Out[6]:
%3 I0 0 0 I0->0 F0 F1 F2 0->F0 1 1 0->1 a 2 2 0->2 b 1->F1 1->1 a 2->F2

The general algorithm introduces spontaneous transitions.

In [7]:
a.multiply(a, 'general')
Out[7]:
%3 I0 0 0 I0->0 F3 F4 F5 1 1 0->1 a 2 2 0->2 b 3 3 0->3 ε 1->1 a 1->3 ε 2->3 ε 3->F3 4 4 3->4 a 5 5 3->5 b 4->F4 4->4 a 5->F5

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

In [8]:
a.multiply(a, 'standard')
Out[8]:
%3 I0 0 0 I0->0 F0 F1 F2 F3 F4 0->F0 1 1 0->1 a 2 2 0->2 b 3 3 0->3 a 4 4 0->4 b 1->F1 1->1 a 1->3 a 1->4 b 2->F2 2->3 a 2->4 b 3->F3 3->3 a 4->F4

The deterministic version returns a deterministic automaton.

In [9]:
a.multiply(a, 'deterministic')
Out[9]:
%3 I0 0 0 I0->0 F0 F1 F2 F3 F4 0->F0 1 1 0->1 a 2 2 0->2 b 1->F1 1->1 a 3 3 1->3 b 2->F2 2->3 b 4 4 2->4 a 3->F3 4->F4 4->4 a

Repeated Multiplication

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

In [10]:
aut('ab') ** 3
Out[10]:
%3 I0 0 0 I0->0 F6 1 1 0->1 a 2 2 1->2 b 3 3 2->3 a 4 4 3->4 b 5 5 4->5 a 6 6 5->6 b 6->F6
In [11]:
aut('a*') * 3
Out[11]:
%3 I0 0 0 I0->0 F0 F1 0->F0 ⟨3⟩ 1 1 0->1 a 1->F1 ⟨3⟩ 1->1 a

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

In [12]:
aut('ab') ** -1
Out[12]:
%3 I0 0 0 I0->0 F0 F2 0->F0 1 1 0->1 a 2 2 1->2 b 2->F2 2->1 a
In [13]:
aut('ab').star()
Out[13]:
%3 I0 0 0 I0->0 F0 F2 0->F0 1 1 0->1 a 2 2 1->2 b 2->F2 2->1 a

Sums of Repeated Multiplications

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

In [14]:
aut('ab') ** (2, 2)
Out[14]:
%3 I0 0 0 I0->0 F4 1 1 0->1 a 2 2 1->2 b 3 3 2->3 a 4 4 3->4 b 4->F4
In [15]:
aut('ab') ** (2, 4)
Out[15]:
%3 I0 0 0 I0->0 F4 F6 F10 1 1 0->1 a 2 2 1->2 b 3 3 2->3 a 4 4 3->4 b 4->F4 5 5 4->5 a 7 7 4->7 a 6 6 5->6 b 6->F6 8 8 7->8 b 9 9 8->9 a 10 10 9->10 b 10->F10
In [16]:
aut('ab') ** (2, -1)
Out[16]:
%3 I0 0 0 I0->0 F4 F6 1 1 0->1 a 2 2 1->2 b 3 3 2->3 a 4 4 3->4 b 4->F4 5 5 4->5 a 6 6 5->6 b 6->F6 6->5 a
In [17]:
aut('ab') ** (-1, 3)
Out[17]:
%3 I0 0 0 I0->0 F0 F2 F6 F12 0->F0 1 1 0->1 a 3 3 0->3 a 7 7 0->7 a 2 2 1->2 b 2->F2 4 4 3->4 b 5 5 4->5 a 6 6 5->6 b 6->F6 8 8 7->8 b 9 9 8->9 a 10 10 9->10 b 11 11 10->11 a 12 12 11->12 b 12->F12
In [18]:
aut('ab').multiply((-1, 3), "deterministic")
Out[18]:
%3 I0 0 0 I0->0 F0 F2 F4 F6 0->F0 1 1 0->1 a 2 2 1->2 b 2->F2 3 3 2->3 a 4 4 3->4 b 4->F4 5 5 4->5 a 6 6 5->6 b 6->F6

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

In [19]:
aut('ab').multiply((-1, 3), "general")
Out[19]:
%3 I0 0 0 I0->0 F1 F4 F10 F19 1 1 0->1 ε 2 2 0->2 ε 5 5 0->5 ε 11 11 0->11 ε 1->F1 3 3 2->3 a 4 4 3->4 b 4->F4 6 6 5->6 a 7 7 6->7 b 8 8 7->8 ε 9 9 8->9 a 10 10 9->10 b 10->F10 12 12 11->12 a 13 13 12->13 b 14 14 13->14 ε 15 15 14->15 a 16 16 15->16 b 17 17 16->17 ε 18 18 17->18 a 19 19 18->19 b 19->F19
In [20]:
aut('ab').multiply((-1, 3), "general").proper()
Out[20]:
%3 I0 0 0 I0->0 F0 F2 F6 F12 0->F0 1 1 0->1 a 3 3 0->3 a 7 7 0->7 a 2 2 1->2 b 2->F2 4 4 3->4 b 5 5 4->5 a 6 6 5->6 b 6->F6 8 8 7->8 b 9 9 8->9 a 10 10 9->10 b 11 11 10->11 a 12 12 11->12 b 12->F12