expression.compose(e)

The composition of two (two-tape) expressions.

Since Python 3.5, can also be written with the infix operator @: e @ f is syntactic sugar for e.compose(f).

See also:

Examples

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

As a simple example, let's compose $a|j+b|j$ with $j|x + k|y$, convert this expression into an automaton, and then extract an expression from it. In other words, let's build an extended expression, and eliminate its compose operator.

In [2]:
e1 = ctx1.expression('a|j + b|k')
e2 = ctx2.expression('j|x* + k|y*')
e = e1 @ e2
e
Out[2]:
$\left(a|j + b|k\right)@\left( \left. j \middle| {x}^{*} \right. + \left. k \middle| {y}^{*} \right. \right)$
In [3]:
a = e.automaton()
a
Out[3]:
%3 I0 0 0 I0->0 ⟨0⟩ F1 F2 F3 1 1 0->1 ⟨0⟩a|ε, ⟨0⟩b|ε 2 2 0->2 ⟨0⟩a|x 3 3 0->3 ⟨0⟩b|y 1->F1 ⟨0⟩ 2->F2 ⟨0⟩ 2->2 ⟨0⟩ε|x 3->F3 ⟨0⟩ 3->3 ⟨0⟩ε|y
In [4]:
a.expression()
Out[4]:
$a|\varepsilon + b|\varepsilon + \left(a|x\right) \, \left(\varepsilon|x\right)^{*} + \left(b|y\right) \, \left(\varepsilon|y\right)^{*}$

Using expression.automaton (aka, expression.derived_term) on the composition of expressions often gives better results than composing the automata:

In [5]:
(e1.automaton() @ e2.automaton()).strip()
Out[5]:
%3 I0 0 0 I0->0 ⟨0⟩ F1 F2 F3 F4 F5 1 1 0->1 ⟨0⟩a|ε, ⟨0⟩b|ε 2 2 0->2 ⟨0⟩a|x 3 3 0->3 ⟨0⟩b|y 1->F1 ⟨0⟩ 2->F2 ⟨0⟩ 4 4 2->4 ⟨0⟩ε|x 3->F3 ⟨0⟩ 5 5 3->5 ⟨0⟩ε|y 4->F4 ⟨0⟩ 4->4 ⟨0⟩ε|x 5->F5 ⟨0⟩ 5->5 ⟨0⟩ε|y

Distance of Edition

In this example (taken from SACS-2017 which was based on mohri.2002.ciaa), we build a Levenshtein automaton which can be used to compute the distance between words and/or languages.

We introduce two weighted expressions: the first one specifies the costs: _I_nserting or _S_uppressng a letter costs 1, but merely copying it is free (cost 0, left implicit).

In [6]:
ctx = vcsn.context("lat<lan(a-zIS), lan(a-zIS)>, zmin")
f1 = ctx.expression('([a-z] + ⟨1⟩(\e|I + [a-z]|S))∗'); f1
Out[6]:
$\left(a|a + b|b + c|c + d|d + e|e + f|f + g|g + h|h + i|i + j|j + k|k + l|l + m|m + n|n + o|o + p|p + q|q + r|r + s|s + t|t + u|u + v|v + w|w + x|x + y|y + z|z + \left\langle 1 \right\rangle \,\left(\varepsilon|I + \left. [\hat{}IS] \middle| S \right. \right)\right)^{*}$

The second specifies what letters can be inserted, and what suppression means.

In [7]:
f2 = ctx.expression('([a-z] + I|[a-z] + S|\e)∗')
f2
Out[7]:
$\left(S|\varepsilon + a|a + b|b + c|c + d|d + e|e + f|f + g|g + h|h + i|i + j|j + k|k + l|l + m|m + n|n + o|o + p|p + q|q + r|r + s|s + t|t + u|u + v|v + w|w + x|x + y|y + z|z + \left. I \middle| [\hat{}IS] \right. \right)^{*}$

Finally, this expression is equivalent to the Levenshtein automaton (for these costs).

In [8]:
f = f1 @ f2
f
Out[8]:
$\left(a|a + b|b + c|c + d|d + e|e + f|f + g|g + h|h + i|i + j|j + k|k + l|l + m|m + n|n + o|o + p|p + q|q + r|r + s|s + t|t + u|u + v|v + w|w + x|x + y|y + z|z + \left\langle 1 \right\rangle \,\left(\varepsilon|I + \left. [\hat{}IS] \middle| S \right. \right)\right)^{*}@\left(S|\varepsilon + a|a + b|b + c|c + d|d + e|e + f|f + g|g + h|h + i|i + j|j + k|k + l|l + m|m + n|n + o|o + p|p + q|q + r|r + s|s + t|t + u|u + v|v + w|w + x|x + y|y + z|z + \left. I \middle| [\hat{}IS] \right. \right)^{*}$
In [9]:
f.automaton()
Out[9]:
%3 I0 0 0 I0->0 ⟨0⟩ F0 0->F0 ⟨0⟩ 0->0 ⟨1⟩[ε|a-ε|za|εb|εc|εd|εe|εf|εg|εh|εi|εj|εk|εl|εm|εn|εo|εp|εq|εr|εs|εt|εu|εv|εw|εx|εy|εz|ε], ⟨0⟩[a|ab|bc|cd|de|ef|fg|gh|hi|ij|jk|kl|lm|mn|no|op|pq|qr|rs|st|tu|uv|vw|wx|xy|yz|z]

The edit distance between train and plane is

In [10]:
(ctx.expression('train') @ f1 @ f2 @ ctx.expression('plane')).shortest(3)
Out[10]:
$\left\langle 6\right\rangle \mathit{train}|\mathit{plane}$