expression.shuffle(exp)

$\newcommand{\Ed}{\mathsf{E}}% \newcommand{\Fd}{\mathsf{F}}% \newcommand{\Gd}{\mathsf{G}}% \newcommand{\infiltrate}{\mathbin{\uparrow}}% \newcommand{\shuffle}{\mathbin{\between}}$ The shuffle product of expressions.

See also:

Examples

In [1]:
import vcsn

Boolean Automata

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

In [2]:
a = vcsn.B.expression('abc')
a
Out[2]:
$a \, b \, c$
In [3]:
b = vcsn.B.expression('xyz')
b
Out[3]:
$x \, y \, z$
In [4]:
shuff = a.shuffle(b)
shuff
Out[4]:
$a \, b \, c \between x \, y \, z$
In [5]:
shuff.automaton()
Out[5]:
%3 I0 0 0 I0->0 F9 1 1 0->1 a 2 2 0->2 x 3 3 1->3 x 14 14 1->14 b 2->3 a 4 4 2->4 y 5 5 3->5 y 12 12 3->12 b 4->5 a 6 6 4->6 z 7 7 5->7 z 10 10 5->10 b 6->7 a 8 8 7->8 b 9 9 8->9 c 9->F9 10->8 z 11 11 10->11 c 11->9 z 12->10 y 13 13 12->13 c 13->11 y 14->12 x 15 15 14->15 c 15->13 x

Weighted expressions

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

In [6]:
exp = vcsn.Z.expression
a = exp('<2>a<3>b', 'trivial')
b = exp('<4>x<-2>y', 'trivial')
a.shuffle(b).automaton()
Out[6]:
%3 I0 0 0 I0->0 F6 1 1 0->1 ⟨2⟩a 2 2 0->2 ⟨4⟩x 3 3 1->3 ⟨4⟩x 8 8 1->8 ⟨3⟩b 2->3 ⟨2⟩a 4 4 2->4 ⟨-2⟩y 5 5 3->5 ⟨-2⟩y 7 7 3->7 ⟨3⟩b 4->5 ⟨2⟩a 6 6 5->6 ⟨3⟩b 6->F6 7->6 ⟨-2⟩y 8->7 ⟨4⟩x

Associativity

The operator is associative: $(\Ed \shuffle \Fd) \shuffle \Gd \equiv \Ed \shuffle (\Fd \shuffle \Gd)$, i.e., both expressions denote the same series.

In [7]:
x = exp('<2>a', 'trivial')
y = exp('<3>a', 'trivial')
z = exp('<4>a', 'trivial')
(x.shuffle(y)).shuffle(z).automaton()
Out[7]:
%3 I0 0 0 I0->0 F6 1 1 0->1 ⟨4⟩a 2 2 0->2 ⟨3⟩a 3 3 0->3 ⟨2⟩a 4 4 1->4 ⟨2⟩a 7 7 1->7 ⟨3⟩a 5 5 2->5 ⟨2⟩a 2->7 ⟨4⟩a 3->4 ⟨4⟩a 3->5 ⟨3⟩a 6 6 4->6 ⟨3⟩a 5->6 ⟨4⟩a 6->F6 7->6 ⟨2⟩a
In [8]:
x.shuffle(y.shuffle(z)).automaton()
Out[8]:
%3 I0 0 0 I0->0 F6 1 1 0->1 ⟨4⟩a 2 2 0->2 ⟨3⟩a 3 3 0->3 ⟨2⟩a 4 4 1->4 ⟨2⟩a 7 7 1->7 ⟨3⟩a 5 5 2->5 ⟨2⟩a 2->7 ⟨4⟩a 3->4 ⟨4⟩a 3->5 ⟨3⟩a 6 6 4->6 ⟨3⟩a 5->6 ⟨4⟩a 6->F6 7->6 ⟨2⟩a