# automaton.compose(aut, lazy=False)¶

The (accessible part of the) composition of two transducers ($\mathcal{A}_1$ and $\mathcal{A}_2$).

Preconditions:

• $\mathcal{A}_1$ and $\mathcal{A}_2$ are transducers
• $\mathcal{A}_1$ has at least 2 tapes
• The second tape of $\mathcal{A}_1$ must have the same labelset as the first tape of $\mathcal{A}_2$

Postconditions:

• $\forall u \in alphabet(\mathcal{A}_1)^*, \; \mathcal{A}_2.eval(\mathcal{A}_1.eval(u)) = \mathcal{A}_1.compose(\mathcal{A}_2).eval(u)$

## Examples¶

In [1]:
import vcsn
ctx1 = vcsn.context("lat<lal<char(ab)>, lal<char(jk)>>, b")
ctx2 = vcsn.context("lat<lal<char(jk)>, lal<char(xy)>>, b")

In [2]:
a1 = ctx1.expression("(a|k)(a|j) + (b|k)*").automaton()
a1

Out[2]:
In [3]:
a2 = ctx2.expression("(k|y)(k|x)*").automaton()
a2

Out[3]:

The result of the composition has a useless state. Note that only the accessible part has been computed.

In [4]:
a1.compose(a2)

Out[4]:

### Translations¶

The composition of a "translator" from French to English with one from English to Spanish is analogous to the computation of the French to Spanish "translator".

In [5]:
%%file fr2en
chien|dog
chat|cat

Overwriting fr2en

In [6]:
ctx = vcsn.context("lat<lan<char>, lan<char>>, b")
fr_to_en = ctx.trie(filename='fr2en')
fr_to_en

Out[6]:
In [7]:
en_to_es = ctx.expression("dog|perro + cat|gato").automaton()
en_to_es

Out[7]:
In [8]:
fr_to_es = fr_to_en.compose(en_to_es)
fr_to_es

Out[8]:

The states are decorated: they are pairs of states of both automata. For technical reason, to ensure correctness of the result, since this is a composition between automata with spontaneous transition, the second automaton was "insplit": its states with both proper and spontaneous transitions (such as state 5), were split in two: a state swith only incoming proper transitions (labeled with $!\varepsilon$) and a state with only incoming spontaneous transitions (labeled with $\varepsilon$). See automaton.insplit for more details.

To remove the decoration, use automaton.strip.

In [9]:
fr_to_es.strip()

Out[9]:

### Lazy composition¶

The composition can be computed on-the-fly. This is especially useful when composing two large automata with a small one: one will only compute the parts of the large composition that are needed for the small composition.

In [10]:
fr_to_es_lazy = fr_to_en.compose(en_to_es, lazy=True)
fr_to_es_lazy

Out[10]:
In [11]:
chien = ctx.expression("chien|chien").automaton()
chien.compose(fr_to_es_lazy)

Out[11]:

The state $8, (5, !\varepsilon)$ is unresolved, and will only be computed when necessary.

In [12]:
fr_to_es_lazy

Out[12]:

### Relying on "string-letters"¶

This example follows the same path, but using letters that are strings.

In [13]:
ctx = vcsn.context("lat<lan<string>, lan<string>>, b")
ctx

Out[13]:
$(\{\ldots\})^? \times (\{\ldots\})^?\to\mathbb{B}$
In [14]:
%%file fr2en
'chien'|'dog'
'chat'|'cat'
'oiseau'|'bird'
'souris'|'mouse'
'souris'|'mice'

Overwriting fr2en

In [15]:
fr2en = ctx.trie(filename='fr2en')
fr2en

Out[15]:
In [16]:
%%file en2es
'dog'|'perro'
'cat'|'gato'
'mouse'|'ratón'
'mice'|'ratones'

Overwriting en2es

In [17]:
en2es = ctx.trie(filename='en2es')
en2es

Out[17]:
In [18]:
fr2en.compose(en2es)

Out[18]: