automaton.shuffle(a1, ...)

The (accessible part of the) shuffle product of automata.

Preconditions:

  • all the labelsets are letterized

See also:

Examples


In [1]:
import vcsn


:0: FutureWarning: IPython widgets are experimental and may change in the future.

Boolean Automata

The shuffle product of automata computes the shuffling of their languages: all the possible interleavings.


In [2]:
std = lambda exp: vcsn.B.expression(exp).standard()
a = std('abc')
a


Out[2]:
%3 I0 0 0 I0->0 F4 1 1 0->1 a 3 3 1->3 b 4 4 3->4 c 4->F4

In [3]:
a.shuffle(std('xyz'))


Out[3]:
%3 I0 0 0, 0 I0->0 F15 1 1, 0 0->1 a 2 0, 1 0->2 x 3 3, 0 1->3 b 4 1, 1 1->4 x 2->4 a 5 0, 3 2->5 y 6 4, 0 3->6 c 7 3, 1 3->7 x 4->7 b 8 1, 3 4->8 y 5->8 a 9 0, 4 5->9 z 10 4, 1 6->10 x 7->10 c 11 3, 3 7->11 y 8->11 b 12 1, 4 8->12 z 9->12 a 13 4, 3 10->13 y 11->13 c 14 3, 4 11->14 z 12->14 b 15 4, 4 13->15 z 14->15 c 15->F15

Weighted automata

In the case of weighted automata, weights are "kept" with the letters.


In [4]:
c = vcsn.context('lal_char, seriesset<lal_char, z>')
std = lambda exp: c.expression(exp).standard()

In [5]:
std('<A>a<B>b').shuffle(std('<X>x<Y>y'))


Out[5]:
%3 I0 0 0, 0 I0->0 F8 1 1, 0 0->1 ⟨A⟩a 2 0, 1 0->2 ⟨X⟩x 3 3, 0 1->3 ⟨B⟩b 4 1, 1 1->4 ⟨X⟩x 2->4 ⟨A⟩a 5 0, 3 2->5 ⟨Y⟩y 6 3, 1 3->6 ⟨X⟩x 4->6 ⟨B⟩b 7 1, 3 4->7 ⟨Y⟩y 5->7 ⟨A⟩a 8 3, 3 6->8 ⟨Y⟩y 7->8 ⟨B⟩b 8->F8

Associativity

This operator is associative, and it is actually implemented as a variadic operator; a.shuffle(b, c) is not exactly the same as a.shuffle(b).shuffle(c): they are the same automata, but the former is labeled with 3-uples, not 2-tuples.


In [6]:
x = std('<x>a')
y = std('<y>a')
z = std('<z>a')

In [7]:
x.shuffle(y, z)


Out[7]:
%3 I0 0 0, 0, 0 I0->0 F7 1 1, 0, 0 0->1 ⟨x⟩a 2 0, 1, 0 0->2 ⟨y⟩a 3 0, 0, 1 0->3 ⟨z⟩a 4 1, 1, 0 1->4 ⟨y⟩a 5 1, 0, 1 1->5 ⟨z⟩a 2->4 ⟨x⟩a 6 0, 1, 1 2->6 ⟨z⟩a 3->5 ⟨x⟩a 3->6 ⟨y⟩a 7 1, 1, 1 4->7 ⟨z⟩a 5->7 ⟨y⟩a 6->7 ⟨x⟩a 7->F7

In [8]:
x.shuffle(y).shuffle(z)


Out[8]:
%3 I0 0 (0, 0), 0 I0->0 F7 1 (1, 0), 0 0->1 ⟨x⟩a 2 (0, 1), 0 0->2 ⟨y⟩a 3 (0, 0), 1 0->3 ⟨z⟩a 4 (1, 1), 0 1->4 ⟨y⟩a 5 (1, 0), 1 1->5 ⟨z⟩a 2->4 ⟨x⟩a 6 (0, 1), 1 2->6 ⟨z⟩a 3->5 ⟨x⟩a 3->6 ⟨y⟩a 7 (1, 1), 1 4->7 ⟨z⟩a 5->7 ⟨y⟩a 6->7 ⟨x⟩a 7->F7