# Quotient Operators for Weighted Rational Expressions¶

You may change the cells, and run then. To run a cell in a notebook, hit "Control-Enter" (in which case the focus stays on the same cell) or "Shift-Enter" (focus goes to the next cell). Beware that depending on the requested operations, Vcsn may generate and compile code, which may be a really slow process on small machines (about a minute): be patient! However, the code is compiled only once: successive uses will be way faster.

To run all the cells anew, select "Restart & Run All" in the "Kernel" menu above.

In :
import sys
import vcsn


## Section 2, Notations¶

First we introduce the "context" we are interested in: labels are letter-or-empty-word ("lan": labels are nullable), values are rational numbers.

In :
Q = vcsn.context('lan, q')
Q

Out:
$(\{\ldots\})^?\to\mathbb{Q}$

### Expressions¶

The rational expressions in Vcsn supports several operators beyond the classical ones. See Expressions for all the details. The following examples should be self-explanatory.

In :
e1 = Q.expression('[ab]'); e1

Out:
$a + b$
In :
e1.star()

Out:
$\left(a + b\right)^{*}$
In :
2 * e1 + e1 * e1.star()

Out:
$\left\langle 2 \right\rangle \,\left(a + b\right) + \left(a + b\right) \, \left(a + b\right)^{*}$

### Expansions¶

One can play with the different operations on expansions. However, there is no direct means to enter an expansion, one has to compute the expansion of an expression.

In :
e1 = Q.expression('ab')
x1 = e1.expansion()
x1

Out:
$a \odot \left[b\right]$
In :
e2 = Q.expression('[ab]*')
x2 = e2.expansion()
x2

Out:
$\left\langle 1\right\rangle \oplus a \odot \left[\left(a + b\right)^{*}\right] \oplus b \odot \left[\left(a + b\right)^{*}\right]$

The left-quotient is denoted {\} in the syntax of Vcsn's expressions, but we use Python's operator // to denote it. So e // f denotes e {\} f.

In :
x2 // x1

Out:
$\varepsilon \odot \left[a \, b \oplus \left(a + b\right)^{*} \backslash b\right]$
In :
x1 // x2

Out:
$\varepsilon \odot \left[a \, b \backslash \varepsilon \oplus b \backslash \left(a + b\right)^{*}\right]$

### Derivative¶

Although not covered in the paper, Vcsn does support the derivatives. However, the quotient operator is not supported.

In :
e = Q.expression('<2>[ab]*')
e

Out:
$\left\langle 2 \right\rangle \,\left(a + b\right)^{*}$
In :
e.constant_term()

Out:
$2$
In :
e.derivation('a')

Out:
$\left\langle 2\right\rangle \left(a + b\right)^{*}$
In :
e.derivation('b')

Out:
$\left\langle 2\right\rangle \left(a + b\right)^{*}$

Those three facts, constant term and derivative wrt $a$ and $b$, are fully captured by this expansion.

In :
e.expansion()

Out:
$\left\langle 2\right\rangle \oplus a \odot \left[\left\langle 2\right\rangle \left(a + b\right)^{*}\right] \oplus b \odot \left[\left\langle 2\right\rangle \left(a + b\right)^{*}\right]$

## Example $\mathsf{E}_1$: A Simple Expression¶

In Vcsn, the left-quotient is written {\} (because the backslash character is used to escape operators, e.g., \* denotes the letter *, not the Kleene star). The expression $\mathsf{E}_1$ is therefore:

In :
e1 = Q.expression('(<2>a) {\} (<3>[ab] + <5>aa* + <7>ab*) + <11>ab*')
e1

Out:
$\left\langle 11 \right\rangle \,\left(a \, {b}^{*}\right) + \left\langle 2 \right\rangle \,a \backslash \left( \left\langle 3 \right\rangle \,\left(a + b\right) + \left\langle 5 \right\rangle \,\left(a \, {a}^{*}\right) + \left\langle 7 \right\rangle \,\left(a \, {b}^{*}\right)\right)$

Its expansion is (contrary to the paper, the empty expression is denoted $\varepsilon$ instead of $\mathsf{1}$):

In :
e1.expansion()

Out:
$\left\langle 6\right\rangle \oplus \varepsilon \odot \left[\left\langle 10\right\rangle {a}^{*} \oplus \left\langle 14\right\rangle {b}^{*}\right] \oplus a \odot \left[\left\langle 11\right\rangle {b}^{*}\right]$

For sake of performance, the constant term is actually kept separate in our implementation of expansions. The previous result, rewritten in the style of the paper, is exactly the same:

$$# \left\langle 6\right\rangle \oplus \varepsilon \odot \left[\left\langle 10\right\rangle {a}^{} \oplus \left\langle 14\right\rangle {b}^{}\right] \oplus a \odot \left[\left\langle 11\right\rangle {b}^{*}\right]¶ \varepsilon \odot \left[ \left\langle 6\right\rangle \odot \varepsilon \oplus \left\langle 10\right\rangle \odot {a}^{} \oplus \left\langle 14\right\rangle \odot {b}^{}\right] \oplus a \odot \left[\left\langle 11\right\rangle \odot {b}^{*}\right]$$

The derived-term automaton of $\mathsf{E}_1$, $\mathcal{A}_{\mathsf{E}_1}$, is:

In :
a1 = e1.derived_term()
a1

Out:

## Example 5: Not all the States are Coaccessible¶

In :
e = Q.expression('(<1/2>ab {\} ab*)*')
e

Out:
$\left( \left\langle \frac{1}{2} \right\rangle \,\left(a \, b\right) \backslash a \, {b}^{*}\right)^{*}$
In :
e.expansion()

Out:
$\left\langle 1\right\rangle \oplus \varepsilon \odot \left[\left\langle \frac{1}{2}\right\rangle \left(b \backslash {b}^{*}\right) \, \left( \left\langle \frac{1}{2} \right\rangle \,\left(a \, b\right) \backslash a \, {b}^{*}\right)^{*}\right]$
In :
a = e.derived_term()
a

Out:

As such, this automaton in $\mathbb{Q}$ is invalid: it contains a spontaneous loop whose weight, 1, is not starrable.

In :
a.is_valid()

Out:
False

Once trimmed, it is valid though, and its spontaneous transitions may be removed.

In :
a.trim()

Out:
In :
a.trim().proper()

Out:

A (basic) rational expression is therefore:

In :
a.trim().proper().expression()

Out:
$\left\langle 2 \right\rangle \,\varepsilon + \left\langle 2 \right\rangle \,\left(b \, \left( \left\langle 2 \right\rangle \,b\right)^{*}\right)$

## Example 6¶

The following expression in invalid in $\mathbb{Q}$, but valid in $\mathbb{B}$.

In :
e = Q.expression('(ab {\} ab)*')
a = e.derived_term()
a

Out:
In :
a.is_valid()

Out:
False

This is because the weight of the spontaneous cycle, 1, is not starrable:

In :
w = Q.weight('1')
w

Out:
$1$
In :
try:
w.star()
except RuntimeError as e:
print(e, file=sys.stderr)

Q: value is not starrable: 1


But in $\mathbb{B}$, it is well defined (Vcsn uses $\top$ to denote True, and $\bot$ for False):

In :
B = vcsn.context('lan, b')
B

Out:
$(\{\ldots\})^?\to\mathbb{B}$
In :
w = B.weight('1')
w

Out:
$\top$
In :
w.star()

Out:
$\top$

Hence the automaton is valid.

In :
e = B.expression('(ab {\} ab)*')
a = e.derived_term()
a

Out:
In :
a.is_valid()

Out:
True
In :
a.proper()

Out:

## Section 5: Transpose and Right Quotient¶

The right quotient is written as {/}, and transpose as a postfix operator {T}.

The following simple example shows how transpose is handled.

In :
e = Q.expression('(abc)*{T}')
e

Out:
${\left(a \, b \, c\right)^{*}}^{T}$
In :
e.expansion()

Out:
$\left\langle 1\right\rangle \oplus c \odot \left[\left(a \, b\right)^{T} \, {\left(a \, b \, c\right)^{*}}^{T}\right]$
In :
e.derived_term()

Out:

Then with a right quotient.

In :
e = Q.expression('aba {/} ba')
e

Out:
$\left(\left(b \, a\right)^{T} \backslash \left(a \, b \, a\right)^{T}\right)^{T}$
In :
e.derived_term()

Out:

### Example 7¶

The following example, in $\mathbb{B}$, computes the suffixes of the language $ab$.

In :
e = B.expression('(ab){/}[ab]*')
e

Out:
$\left({\left(a + b\right)^{*}}^{T} \backslash \left(a \, b\right)^{T}\right)^{T}$
In :
a = e.derived_term()
a

Out:
In :
a.trim().proper().determinize().minimize()

Out: