Rational expressions, or expressions for short, denote (rational) languages in a compact way. Since Vcsn supports weighted expressions, they actually can denoted rational series.
This page documents the syntax and transformations (called identities) that are applied to every expression. The list of available algorithms using expression is in the Algorithms page.
The syntax for rational expressions is as follows (with increasing precedence):
\z, the empty expression.\e, the empty word.a, the letter a.'l', the label l (useful, for instance, when labels are words, or to denote a letter which is an operator: '+' denotes the + letter).[abcd], letter class, equivalent to (a+b+c+d).[a-d], one letter of the current alphabet between a and d. If the alphabet is $\{a, d, e\}$, [a-d] denotes [ad], not [abcd].[^a-dz], one letter of the current alphabet that is not part of [a-dz].[^], any letter of the current alphabet ("any letter other that none").(e), e.e+f, the addition (disjunction, union) of e and f (note the use of +, | is not accepted).e&f, the conjunction (intersection) of e and f.e:f, the shuffle product (interleaving) of e and f.e&:f, the infiltration of e and f.ef and e.f, the multiplication (concatenation) of e and f.<k>e, the left exterior product (left-scalar product) of e by k.e<k>, the right exterior product (right-scalar product) of e by k.e* and e{*}, any number of repetitions of e (the Kleene closure of e).e{n}, the power (repeated multiplication) of e n times: ee ... e.e{n,m}, any repetition of e between n and m, i.e., the sum of the powers of e between n and m: e{n}+e{n+1}+ ... +e{m}.e{n,}, the sum of powers of e at least n times: e{n}e*.e{,m}, at most m repetitions of e: e{0,m}.e{+}, at least one e: e{1,}.e?, e{?}, e optional: e{0,1}.e{c}, the complement of e.where e and f denote expressions, a a label, k a weight, and n and m natural numbers.
Please note that contrary to "regexps" (as in grep, perl, etc.):
+ denotes the choice, not |. denotes the concatenation, use [^] to mean "any letter"Some rewriting rules are applied on the expressions to "simplify" them. The strength of this simplification is graduated.
none: no identities at all. Some algorithms, such as derived_term, might not terminate.trivial: the trivial identities only are applied.associative: the associative identities are added.linear: the linear identities are added. This is the default.distributive: the distributive identities are added.where $\Ed$ stands for any rational expression, $a \in A$~is any letter, $\ell\in A \cup \{\eword\}$, $k, h\in \K$ are weights, and $\lmulq{k}{\ell}$ denotes either $\lmul{k}{\ell}$, or $\ell$ in which case $k = \unK$ in the right-hand side. Any subexpression of a form listed to the left of a '$\Rightarrow$' is rewritten as indicated on the right.
In addition to the trivial identities, the binary operators (addition, conjunction, multiplication) are made associative. Actually, they become variadic instead of being strictly binary. $$ \begin{align} \Ed+(\Fd+\Gd) & \Rightarrow \Ed+\Fd+\Gd\\ \Ed(\Fd\Gd) & \Rightarrow \Ed\Fd\Gd\\ \Ed\&(\Fd\&\Gd) & \Rightarrow \Ed\&\Fd\&\Gd\\ \end{align} $$
In addition to the associative identities, the addition is made commutative. Actually, members of sums are now sorted, and weights of equal terms are added. Some identities requires the weightset to be a commutative semiring (i.e., the product of scalars is commutative). $$ \begin{align} \Fd+\Ed & \Rightarrow \Ed+\Fd && \text{if $\Ed < \Fd$} \\ \lmul{k}{\Ed}+\lmul{h}{\Ed} & \Rightarrow \lmul{k+h}{\Ed}\\ \rmul{\Ed}{k} & \Rightarrow \lmul{k}{\Ed} && \text{if commutative} \\ \lmul{k}{\Ed}\lmul{h}{\Fd} & \Rightarrow \lmul{kh}{(\Ed\Fd)} && \text{if commutative} \\ \end{align} $$
In addition to the linear identities, the multiplication and multiplication by a scalar are distributed on the sum. $$ \begin{gather*} \lmul{k}{(\Ed+\Fd)} \Rightarrow \lmul{k}{\Ed} + \lmul{k}{\Fd} \\ \Ed(\Fd+\Gd) \Rightarrow \Ed\Fd + \Ed\Gd \qquad (\Ed+\Fd)\Gd \Rightarrow \Ed\Gd + \Fd\Gd \\ \end{gather*} $$
In [1]:
import vcsn
import pandas as pd
pd.options.display.max_colwidth = 0
The following helping routine takes a list of expressions as text (*es), converts them into genuine expression objects (ctx.expression(e, id)) for each id, formats them into LaTeX, and puts them in a DataFrame for display.
In [2]:
ids = ['trivial', 'associative', 'linear', 'distributive']
ctx = vcsn.context('lal_char(a-z), b')
def example(*es):
res = []
for e in es:
res.append([e] + ['$' + ctx.expression(e, id).format('latex') + '$' for id in ids])
return pd.DataFrame(res, columns=['Input'] + list(map(str.title, ids)))
In [3]:
example('a', 'a+b+c', 'a+(b+c)', 'a+b+c+d', 'b+a', '[ab][ab]')
Out[3]:
A few more examples, with weights in $\mathbb{Q}$:
In [4]:
ctx = vcsn.Q
example('a', 'a+a+a', 'a+a+b', 'a+b+a', '<2>(a+b)', '([ab]+[ab]){2}', '<2>ab<3>cd<5>')
Out[4]:
In [5]:
from ipywidgets import interact_manual
from IPython.display import display
es = []
@interact_manual
def interactive_example(expression = "[ab]{3,}"):
es.append(expression)
display(example(*es))