automaton.compose.ipynb

Kernel: Python 3

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.evaluate(\mathcal{A}_1.evaluate(u)) = \mathcal{A}_1.compose(\mathcal{A}_2).evaluate(u)$

See also:

• automaton.insplit

Examples

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

a1 = ctx1.expression("(a|k)(a|j) + (b|k)*").automaton()
a1

a2 = ctx2.expression("(k|y)(k|x)*").automaton()
a2

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

a1.compose(a2)

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".

%%file fr2en
chien|dog
chat|cat

Overwriting fr2en

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

en_to_es = ctx.expression("dog|perro + cat|gato").automaton()
en_to_es

fr_to_es = fr_to_en.compose(en_to_es)
fr_to_es

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.

fr_to_es.strip()

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.

fr_to_es_lazy = fr_to_en.compose(en_to_es, lazy=True)
fr_to_es_lazy

chien = ctx.expression("chien|chien").automaton()
chien.compose(fr_to_es_lazy)

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

fr_to_es_lazy

Relying on "string-letters"

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

ctx = vcsn.context("lat<lan<string>, lan<string>>, b")
ctx

$(\{\ldots\})^? \times (\{\ldots\})^?\to\mathbb{B}$

%%file fr2en
'chien'|'dog'
'chat'|'cat'
'oiseau'|'bird'
'souris'|'mouse'
'souris'|'mice'

Overwriting fr2en

fr2en = ctx.trie(filename='fr2en')
fr2en

%%file en2es
'dog'|'perro'
'cat'|'gato'
'mouse'|'ratón'
'mice'|'ratones'

Overwriting en2es

en2es = ctx.trie(filename='en2es')
en2es

fr2en.compose(en2es)