expression.derivation(label,breaking=False)

Compute the derivation of a weighted expression.

Arguments:

  • label: the (non empty) string to derive the expression with.
  • breaking: whether to split the result.

See also:

References:

Examples

The following function will prove handy: it takes a rational expression and a list of strings, and returns a $\LaTeX$ aligned environment to display nicely the result.

In [1]:
import vcsn
from IPython.display import Latex

def diffs(e, ws):
    eqs = []
    for w in ws:
        w = e.context().word(w)
        eqs.append(r'\frac{{\partial}}{{\partial {0:x}}} {1:x}& = {2:x}'
                   .format(w, e, e.derivation(w)))
    return Latex(r'''\begin{{aligned}}
        {0}
    \end{{aligned}}'''.format(r'\\'.join(eqs)))

Classical expressions

In the classical case (labels are letters, and weights are Boolean), this is the construct as described by Antimirov.

In [2]:
b = vcsn.context('lal_char(ab), b')
e = b.expression('[ab]{3}')
e.derivation('a')
Out[2]:
$\left(a + b\right)^{2}$

Or, using the diffs function we defined above:

In [3]:
diffs(e, ['a', 'aa', 'aaa', 'aaaa'])
Out[3]:
\begin{aligned} \frac{\partial}{\partial \mathit{a}} \left(a + b\right)^{3}& = \left(a + b\right)^{2}\\\frac{\partial}{\partial \mathit{aa}} \left(a + b\right)^{3}& = a + b\\\frac{\partial}{\partial \mathit{aaa}} \left(a + b\right)^{3}& = \varepsilon\\\frac{\partial}{\partial \mathit{aaaa}} \left(a + b\right)^{3}& = \emptyset \end{aligned}

Weighted Expressions

Of course, expressions can be weighted.

In [4]:
q = vcsn.context('lal_char(abc), q')
e = q.expression('(<1/6>a*+<1/3>b*)*')
diffs(e, ['a', 'aa', 'ab', 'b', 'ba', 'bb'])
Out[4]:
\begin{aligned} \frac{\partial}{\partial \mathit{a}} \left( \left\langle \frac{1}{6} \right\rangle \,{a}^{*} + \left\langle \frac{1}{3} \right\rangle \,{b}^{*}\right)^{*}& = \left\langle \frac{1}{3}\right\rangle {a}^{*} \, \left( \left\langle \frac{1}{6} \right\rangle \,{a}^{*} + \left\langle \frac{1}{3} \right\rangle \,{b}^{*}\right)^{*}\\\frac{\partial}{\partial \mathit{aa}} \left( \left\langle \frac{1}{6} \right\rangle \,{a}^{*} + \left\langle \frac{1}{3} \right\rangle \,{b}^{*}\right)^{*}& = \left\langle \frac{4}{9}\right\rangle {a}^{*} \, \left( \left\langle \frac{1}{6} \right\rangle \,{a}^{*} + \left\langle \frac{1}{3} \right\rangle \,{b}^{*}\right)^{*}\\\frac{\partial}{\partial \mathit{ab}} \left( \left\langle \frac{1}{6} \right\rangle \,{a}^{*} + \left\langle \frac{1}{3} \right\rangle \,{b}^{*}\right)^{*}& = \left\langle \frac{2}{9}\right\rangle {b}^{*} \, \left( \left\langle \frac{1}{6} \right\rangle \,{a}^{*} + \left\langle \frac{1}{3} \right\rangle \,{b}^{*}\right)^{*}\\\frac{\partial}{\partial \mathit{b}} \left( \left\langle \frac{1}{6} \right\rangle \,{a}^{*} + \left\langle \frac{1}{3} \right\rangle \,{b}^{*}\right)^{*}& = \left\langle \frac{2}{3}\right\rangle {b}^{*} \, \left( \left\langle \frac{1}{6} \right\rangle \,{a}^{*} + \left\langle \frac{1}{3} \right\rangle \,{b}^{*}\right)^{*}\\\frac{\partial}{\partial \mathit{ba}} \left( \left\langle \frac{1}{6} \right\rangle \,{a}^{*} + \left\langle \frac{1}{3} \right\rangle \,{b}^{*}\right)^{*}& = \left\langle \frac{2}{9}\right\rangle {a}^{*} \, \left( \left\langle \frac{1}{6} \right\rangle \,{a}^{*} + \left\langle \frac{1}{3} \right\rangle \,{b}^{*}\right)^{*}\\\frac{\partial}{\partial \mathit{bb}} \left( \left\langle \frac{1}{6} \right\rangle \,{a}^{*} + \left\langle \frac{1}{3} \right\rangle \,{b}^{*}\right)^{*}& = \left\langle \frac{10}{9}\right\rangle {b}^{*} \, \left( \left\langle \frac{1}{6} \right\rangle \,{a}^{*} + \left\langle \frac{1}{3} \right\rangle \,{b}^{*}\right)^{*} \end{aligned}

And this is tightly connected with the construction of the derived-term automaton.

In [5]:
e.derived_term()
Out[5]:
%3 I0 0 (⟨1/6⟩a*+⟨1/3⟩b*)* I0->0 F0 F1 F2 0->F0 ⟨2⟩ 1 a*(⟨1/6⟩a*+⟨1/3⟩b*)* 0->1 ⟨1/3⟩a 2 b*(⟨1/6⟩a*+⟨1/3⟩b*)* 0->2 ⟨2/3⟩b 1->F1 ⟨2⟩ 1->1 ⟨4/3⟩a 1->2 ⟨2/3⟩b 2->F2 ⟨2⟩ 2->1 ⟨1/3⟩a 2->2 ⟨5/3⟩b

Multitape expressions

It is possible to compute the derivatives of a multitape expression.

In [6]:
c = vcsn.context('lat<lan(ab), lan(xy)>, q')
exp = c.expression
c
Out[6]:
$(\{a, b\})^? \times (\{x, y\})^?\to\mathbb{Q}$
In [7]:
e = exp('(a{+}|x + b{+}|y)*')
In [8]:
e.derived_term()
Out[8]:
%3 I0 0 (aa*|x+bb*|y)* I0->0 F0 F1 F2 0->F0 1 (a*|ε)(aa*|x+bb*|y)* 0->1 a|x 2 (b*|ε)(aa*|x+bb*|y)* 0->2 b|y 1->F1 1->1 a|ε, a|x 1->2 b|y 2->F2 2->1 a|x 2->2 b|ε, b|y

The following expressions corresponds to the second state of the above automaton (reached from the initial state via $a|x$).

In [9]:
f = exp(r'a*|\e') * e
f
Out[9]:
$\left( \left. {a}^{*} \middle| \varepsilon \right. \right) \, \left( \left. a \, {a}^{*} \middle| x \right. + \left. b \, {b}^{*} \middle| y \right. \right)^{*}$
In [10]:
diffs(f, [r'\e|x', r'\e|y', r'a|\e', r'b|\e'])
Out[10]:
\begin{aligned} \frac{\partial}{\partial \varepsilon|\mathit{x}} \left( \left. {a}^{*} \middle| \varepsilon \right. \right) \, \left( \left. a \, {a}^{*} \middle| x \right. + \left. b \, {b}^{*} \middle| y \right. \right)^{*}& = \emptyset\\\frac{\partial}{\partial \varepsilon|\mathit{y}} \left( \left. {a}^{*} \middle| \varepsilon \right. \right) \, \left( \left. a \, {a}^{*} \middle| x \right. + \left. b \, {b}^{*} \middle| y \right. \right)^{*}& = \emptyset\\\frac{\partial}{\partial \mathit{a}|\varepsilon} \left( \left. {a}^{*} \middle| \varepsilon \right. \right) \, \left( \left. a \, {a}^{*} \middle| x \right. + \left. b \, {b}^{*} \middle| y \right. \right)^{*}& = \left( \left. {a}^{*} \middle| \varepsilon \right. \right) \, \left( \left. a \, {a}^{*} \middle| x \right. + \left. b \, {b}^{*} \middle| y \right. \right)^{*}\\\frac{\partial}{\partial \mathit{b}|\varepsilon} \left( \left. {a}^{*} \middle| \varepsilon \right. \right) \, \left( \left. a \, {a}^{*} \middle| x \right. + \left. b \, {b}^{*} \middle| y \right. \right)^{*}& = \emptyset \end{aligned}
In [11]:
diffs(e, ['a|x', 'a|y', 'b|x', 'b|y'])
Out[11]:
\begin{aligned} \frac{\partial}{\partial \mathit{a}|\mathit{x}} \left( \left. a \, {a}^{*} \middle| x \right. + \left. b \, {b}^{*} \middle| y \right. \right)^{*}& = \left( \left. {a}^{*} \middle| \varepsilon \right. \right) \, \left( \left. a \, {a}^{*} \middle| x \right. + \left. b \, {b}^{*} \middle| y \right. \right)^{*}\\\frac{\partial}{\partial \mathit{a}|\mathit{y}} \left( \left. a \, {a}^{*} \middle| x \right. + \left. b \, {b}^{*} \middle| y \right. \right)^{*}& = \emptyset\\\frac{\partial}{\partial \mathit{b}|\mathit{x}} \left( \left. a \, {a}^{*} \middle| x \right. + \left. b \, {b}^{*} \middle| y \right. \right)^{*}& = \emptyset\\\frac{\partial}{\partial \mathit{b}|\mathit{y}} \left( \left. a \, {a}^{*} \middle| x \right. + \left. b \, {b}^{*} \middle| y \right. \right)^{*}& = \left( \left. {b}^{*} \middle| \varepsilon \right. \right) \, \left( \left. a \, {a}^{*} \middle| x \right. + \left. b \, {b}^{*} \middle| y \right. \right)^{*} \end{aligned}

Breaking derivation

The "breaking" derivation "splits" the polynomial at the end.

In [12]:
e = q.expression('[ab](<2>[ab])', 'associative')
e
Out[12]:
$\left(a + b\right) \, \left\langle 2 \right\rangle \,\left(a + b\right)$
In [13]:
e.derivation('a')
Out[13]:
$ \left\langle 2 \right\rangle \,\left(a + b\right)$
In [14]:
e.derivation('a', True)
Out[14]:
$\left\langle 2\right\rangle a \oplus \left\langle 2\right\rangle b$
In [15]:
e.derivation('a').split()
Out[15]:
$\left\langle 2\right\rangle a \oplus \left\langle 2\right\rangle b$

Again, this is tightly connected with both flavors of the derived-term automaton.

In [16]:
e.derived_term()
Out[16]:
%3 I0 0 (a+b)⟨2⟩(a+b) I0->0 F2 1 ⟨2⟩(a+b) 0->1 a, b 2 ε 1->2 ⟨2⟩a, ⟨2⟩b 2->F2
In [17]:
e.derived_term('breaking_derivation')
Out[17]:
%3 I0 0 a⟨2⟩(a+b) I0->0 I1 1 b⟨2⟩(a+b) I1->1 F4 2 a 0->2 ⟨2⟩a 3 b 0->3 ⟨2⟩a 1->2 ⟨2⟩b 1->3 ⟨2⟩b 4 ε 2->4 a 3->4 b 4->F4