expression.derivation.ipynb

Kernel: Python 3

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:

• expression.derived_term

• expression.expansion

• polynomial.split

References:

• lombardy.2005.tcs defines the derivation

• angrand.2010.jalc defines the breaking derivation

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.

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.

b = vcsn.context('lal_char(ab), b')
e = b.expression('[ab]{3}')
e.derivation('a')

$\left(a + b\right)^{2}$

Or, using the diffs function we defined above:

diffs(e, ['a', 'aa', 'aaa', 'aaaa'])

$$\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.

q = vcsn.context('lal_char(abc), q')
e = q.expression('(<1/6>a*+<1/3>b*)*')
diffs(e, ['a', 'aa', 'ab', 'b', 'ba', 'bb'])

$$\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.

e.derived_term()

Multitape expressions

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

c = vcsn.context('lat<lan(ab), lan(xy)>, q')
exp = c.expression
c

$(\{a, b\})^? \times (\{x, y\})^?\to\mathbb{Q}$

e = exp('(a{+}|x + b{+}|y)*')

e.derived_term()

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

f = exp(r'a*|\e') * e
f

$\left( \left. {a}^{*} \middle| \varepsilon \right. \right) \, \left( \left. a \, {a}^{*} \middle| x \right. + \left. b \, {b}^{*} \middle| y \right. \right)^{*}$

diffs(f, [r'\e|x', r'\e|y', r'a|\e', r'b|\e'])

$$\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}$$

diffs(e, ['a|x', 'a|y', 'b|x', 'b|y'])

$$\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.

e = q.expression('[ab](<2>[ab])', 'associative')
e

$\left(a + b\right) \, \left\langle 2 \right\rangle \,\left(a + b\right)$

e.derivation('a')

$\left\langle 2 \right\rangle \,\left(a + b\right)$

e.derivation('a', True)

$\left\langle 2\right\rangle a \oplus \left\langle 2\right\rangle b$

e.derivation('a').split()

$\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.

e.derived_term()

e.derived_term('breaking_derivation')