The Vcsn platform relies on a central concept: "contexts". They denote typing information about automata, rational expressions, etc. This information is alike a function type: an input type (the label), and an output type (the weight).
Contexts are created by the vcsn.context
function which takes a string as input. This string follows the following syntax:
<context> ::= <labelset> , <weightset>
i.e., a context name is composed of a labelset name, then a comma, then a weightset name.
Different LabelSets model multiple variations on labels, members of a monoid:
letterset<
genset >
Fully defined by an alphabet $A$, its labels being just
letters. It is simply denoted by $A$. It corresponds to the usual
definition of an NFA.
nullableset<
labelset >
Denoted by $A^?$, also defined by an alphabet $A$, its
labels being either letters or the empty word. This corresponds to what
is often called $\varepsilon$-NFAs.
wordset<
genset >
Denoted by $A^*$, also defined by an alphabet $A$, its labels
being (possibly empty) words on this alphabet.
oneset
Denoted by $\{1\}$, containing a single label: 1, the empty word.
tupleset<
labelset1 ,
labelset2 , ...,
labelsetn >
Cartesian product of LabelSets, $L_1 \times \cdots \times
L_n$. This type implements the concept of transducers with an arbitrary
number of "tapes". The concept is developed more in-depth here: Transducers.
The gensets define the types of the letters, and sets of the valid letters. There is currently a single genset type.
char_letters
Specify that the letters are implemented as char
. Any char
will be accepted. The genset is said to be "open".
char_letters(abc...)
Specify that the letters are implemented as char
, and the genset is closed to {a, b, c}
. Any other char
will be rejected.
There are a few abbreviations that are accepted.
lal_char
: letterset<char_letters>
lal_char(abc)
: letterset<char_letters(abc)>
lan_char
: nullableset<letterset<char_letters>>
law_char
: wordset<letterset<char_letters>>
The WeightSets define the semiring of the weights. Builtin weights include:
b
The classical Booleans: $\langle \mathbb{B}, \vee, \wedge, \bot, \top \rangle$
z
The integers coded as int
s: $\langle \mathbb{Z}, +, \times, 0, 1 \rangle$
q
The rationals, coded as pairs of int
s: $\langle \mathbb{Q}, +, \times, 0, 1 \rangle$
qmp
The rationals, with support for multiprecision: $\langle \mathbb{Q}_\text{mp}, +, \times, 0, 1 \rangle$
r
The reals, coded as double
s: $\langle \mathbb{R}, +, \times, 0, 1 \rangle$
nmin
The tropical semiring, coded as unsigned int
s: $\langle \mathbb{N} \cup \{\infty\}, \min, +, \infty, 0 \rangle$
zmin
The tropical semiring, coded as int
s: $\langle \mathbb{Z} \cup \{\infty\}, \min, +, \infty, 0 \rangle$
rmin
The tropical semiring, coded as floats
s: $\langle \mathbb{R} \cup \{\infty\}, \min, +, \infty, 0 \rangle$
log
The log semiring, coded as double
s: $\langle \mathbb{R} \cup \{-\infty, +\infty\}, \oplus_\mathrm{log}, +, +\infty, 0 \rangle$ (where $\oplus_\mathrm{log}$ denotes $x, y \rightarrow - \mathrm{log}(\exp(-x) + \exp(-y))$.
f2
The field: $\langle \mathbb{F}_2, \oplus, \wedge, 0, 1 \rangle$ (where $\oplus$ denotes the "exclusive or").
tupleset
Cartesian product of WeightSets, $W_1 \times \cdots \times W_n$.
In [1]:
import vcsn
vcsn.context('lal<char(abc)>, b')
Out[1]:
If instead of a simple accepter that returns "yes" or "no", you want to compute an integer, work in $\mathbb{Z}$:
In [2]:
vcsn.context('lal<char(abc)>, z')
Out[2]:
To use words on the usual alphabet as labels:
In [3]:
vcsn.context('law<char(a-z)>, z')
Out[3]:
In [4]:
vcsn.context('lat<lal<char(a-f)>, lal<char(A-F)>>, b')
Out[4]:
In [5]:
vcsn.context('lal<char(ab)>, lat<b, z>')
Out[5]:
The following automaton is almost able to recognize $a^nb^n$: it accepts only words of $a^nb^m$ (aka $a^*b^*$) and return $(n, m)$. One still has to check that $n = m$.
In [6]:
zmin2 = vcsn.context('lal<char(ab)>, lat<zmin, zmin>')
zmin2
Out[6]:
In [7]:
ab = zmin2.expression('(<1,0>a)*(<0,0>b)* & (<0,0>a)*(<0,1>b)*')
ab
Out[7]:
In [8]:
a = ab.automaton()
a
Out[8]:
In [9]:
print(a.shortest(len = 4).format('list'))
In [10]:
vcsn.context('''nullableset< lat< lal<char(ba)>,
lat< lan<char(vu)>, law<char(x-z)> >
>
>
,
lat<expressionset<nullableset<lat<lan<char(fe)>, lan<char(hg)>>>,
lat<r, q>>,
lat<b, z>
>
''')
Out[10]: