automaton.compose

The (accessible part of the) composition of two transducers ($A_1$ and $A_2$).

Preconditions:

  • $A_1$ and $A_2$ are transducers
  • $A_1$ has at least 2 tapes
  • The second tape of $A_1$ must have the same labelset as the first tape of $A_2$

Postconditions:

  • $\forall u \in alphabet(A_1)^*, \; A_2.eval(A_1.eval(u)) = A_1.compose(A_2).eval(u)$

See also:

Examples

In [5]:
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 [6]:
a1 = ctx1.expression("(a|k)(a|j) + (b|k)*").automaton()
a1
Out[6]:
%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 [7]:
a2 = ctx2.expression("(k|y)(k|x)*").automaton()
a2
Out[7]:
%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 [8]:
a1.compose(a2)
Out[8]:
%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 [9]:
%%file fr2en
chien|dot
chat|cat

Overwriting fr2en
In [10]:
ctx = vcsn.context("lat<lan<char>, lan<char>>, b")
fr_to_en = ctx.trie('fr2en')
fr_to_en
Out[10]:
%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|t 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 [11]:
en_to_es = ctx.expression("dog|perro + cat|gato").automaton()
en_to_es
Out[11]:
%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 [12]:
fr_to_es = fr_to_en.compose(en_to_es)
fr_to_es
Out[12]:
%3 I0 0 0, 0 I0->0 F7 1 6, 1 0->1 c|g 2 1, 2 0->2 c|p 3 7, 8 1->3 h|a 4 2, 3 2->4 h|e 5 8, 6 3->5 a|t 6 9, 6 5->6 t|ε 7 9, 7 6->7 ε|o 7->F7

Relying on "string-letters"

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

In [13]:
import vcsn
ctx = vcsn.context("lat<lan<string>, lan<string>>, b")
ctx
Out[13]:
$(\{\ldots\})^? \times (\{\ldots\})^?\rightarrow\mathbb{B}$
In [14]:
%%file fr2en
'chien'|'dog'
'chat'|'cat'
'oiseau'|'bird'
'souris'|'mouse'
'souris'|'mice'

Overwriting fr2en
In [15]:
fr2en = ctx.trie('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('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