expression.shuffle.ipynb

Kernel: Python 3

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:

• expression.conjunction

• expression.infiltrate

• automaton.shuffle

Examples

import vcsn

Boolean Automata

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

a = vcsn.B.expression('abc')
a

$a \, b \, c$

b = vcsn.B.expression('xyz')
b

$x \, y \, z$

shuff = a.shuffle(b)
shuff

$a \, b \, c \between x \, y \, z$

shuff.automaton()

Weighted expressions

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

exp = vcsn.Z.expression
a = exp('<2>a<3>b', 'trivial')
b = exp('<4>x<-2>y', 'trivial')
a.shuffle(b).automaton()

Associativity

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

x = exp('<2>a', 'trivial')
y = exp('<3>a', 'trivial')
z = exp('<4>a', 'trivial')
(x.shuffle(y)).shuffle(z).automaton()

x.shuffle(y.shuffle(z)).automaton()