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)$

See also:

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]:
%3 I0 0 0 I0->0 F0 F2 F3 0->F0 1 1 0->1 a|k 2 2 0->2 b|k 3 3 1->3 a|j 2->F2 2->2 b|k 3->F3
In [3]:
a2 = ctx2.expression("(k|y)(k|x)*").automaton()
a2
Out[3]:
%3 I0 0 0 I0->0 F1 1 1 0->1 k|y 1->F1 1->1 k|x

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]:
%3 I0 0 0, 0 I0->0 F2 1 1, 1 0->1 a|y 2 2, 1 0->2 b|y 2->F2 2->2 b|x

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]:
%3 I0 0 0 I0->0 F5 F9 1 1 0->1 c|d 6 6 0->6 c|c 2 2 1->2 h|o 3 3 2->3 i|g 4 4 3->4 e|ε 5 5 4->5 n|ε 5->F5 7 7 6->7 h|a 8 8 7->8 a|t 9 9 8->9 t|ε 9->F9
In [7]:
en_to_es = ctx.expression("dog|perro + cat|gato").automaton()
en_to_es
Out[7]:
%3 I0 0 0 I0->0 F6 1 1 0->1 c|g 2 2 0->2 d|p 7 7 1->7 a|a 3 3 2->3 o|e 4 4 3->4 g|r 5 5 4->5 ε|r 6 6 5->6 ε|o 6->F6 7->5 t|t
In [8]:
fr_to_es = fr_to_en.compose(en_to_es)
fr_to_es
Out[8]:
%3 I0 0 0, (0, !ε) I0->0 F9 F12 1 6, (1, !ε) 0->1 c|g 2 1, (2, !ε) 0->2 c|p 3 7, (7, !ε) 1->3 h|a 4 2, (3, !ε) 2->4 h|e 5 8, (5, !ε) 3->5 a|t 6 3, (4, !ε) 4->6 i|r 7 9, (5, !ε) 5->7 t|ε 8 4, (4, !ε) 6->8 e|ε 9 9, (6, ε) 7->9 ε|o 10 5, (4, !ε) 8->10 n|ε 9->F9 11 5, (5, ε) 10->11 ε|r 12 5, (6, ε) 11->12 ε|o 12->F12

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]:
%3 I0 0 0 I0->0 F9 F12 1 1 0->1 c|g 2 2 0->2 c|p 3 3 1->3 h|a 4 4 2->4 h|e 5 5 3->5 a|t 6 6 4->6 i|r 7 7 5->7 t|ε 8 8 6->8 e|ε 9 9 7->9 ε|o 10 10 8->10 n|ε 9->F9 11 11 10->11 ε|r 12 12 11->12 ε|o 12->F12

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]:
%3 I0 0 0, (0, !ε) I0->0
In [11]:
chien = ctx.expression("chien|chien").automaton()
chien.compose(fr_to_es_lazy)
Out[11]:
%3 I0 0 0, ((0, (0, !ε)), !ε) I0->0 F9 1 1, ((6, (1, !ε)), !ε) 0->1 c|g 2 1, ((1, (2, !ε)), !ε) 0->2 c|p 3 2, ((7, (7, !ε)), !ε) 1->3 h|a 4 2, ((2, (3, !ε)), !ε) 2->4 h|e 5 3, ((3, (4, !ε)), !ε) 4->5 i|r 6 4, ((4, (4, !ε)), !ε) 5->6 e|ε 7 5, ((5, (4, !ε)), !ε) 6->7 n|ε 8 5, ((5, (5, ε)), ε) 7->8 ε|r 9 5, ((5, (6, ε)), ε) 8->9 ε|o 9->F9

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

In [12]:
fr_to_es_lazy
Out[12]:
%3 I0 0 0, (0, !ε) I0->0 F10 1 6, (1, !ε) 0->1 c|g 2 1, (2, !ε) 0->2 c|p 3 7, (7, !ε) 1->3 h|a 4 2, (3, !ε) 2->4 h|e 5 8, (5, !ε) 3->5 a|t 6 3, (4, !ε) 4->6 i|r 7 4, (4, !ε) 6->7 e|ε 8 5, (4, !ε) 7->8 n|ε 9 5, (5, ε) 8->9 ε|r 10 5, (6, ε) 9->10 ε|o 10->F10

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]:
%3 I0 0 0 I0->0 F1 F2 F3 F4 F5 1 1 0->1 'chien'|'dog' 2 2 0->2 'chat'|'cat' 3 3 0->3 'oiseau'|'bird' 4 4 0->4 'souris'|'mouse' 5 5 0->5 'souris'|'mice' 1->F1 2->F2 3->F3 4->F4 5->F5
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]:
%3 I0 0 0 I0->0 F1 F2 F3 F4 1 1 0->1 'dog'|'perro' 2 2 0->2 'cat'|'gato' 3 3 0->3 'mouse'|'ratón' 4 4 0->4 'mice'|'ratones' 1->F1 2->F2 3->F3 4->F4
In [18]:
fr2en.compose(en2es)
Out[18]:
%3 I0 0 0, (0, !ε) I0->0 F1 F2 F3 F4 1 2, (2, !ε) 0->1 'chat'|'gato' 2 1, (1, !ε) 0->2 'chien'|'perro' 3 5, (4, !ε) 0->3 'souris'|'ratones' 4 4, (3, !ε) 0->4 'souris'|'ratón' 1->F1 2->F2 3->F3 4->F4