Contexts
Contexts are central concept of Vcsn: 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:
i.e., a context name is composed of a labelset name, then a comma, then a weightset name.
Labelsets
Different LabelSets model multiple variations on labels, members of a monoid:
letterset<
genset>
Fully defined by an alphabet , its labels being just letters. It is simply denoted by . It corresponds to the usual definition of an NFA.nullableset<
labelset>
Denoted by , also defined by an alphabet , its labels being either letters or the empty word. This corresponds to what is often called -NFAs.wordset<
genset>
Denoted by , also defined by an alphabet , its labels being (possibly empty) words on this alphabet.oneset
Denoted by , containing a single label: 1, the empty word.tupleset<
labelset1,
labelset2, ...,
labelsetn>
Cartesian product of LabelSets, . This type implements the concept of transducers with an arbitrary number of "tapes". The concept is developed more in-depth here: Transducers.
Gensets
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 aschar
. Anychar
will be accepted. The genset is said to be "open".char_letters(abc...)
Specify that the letters are implemented aschar
, and the genset is closed to{a, b, c}
. Any otherchar
will be rejected.
Abbreviations for Labelsets
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>>
Weightsets
The WeightSets define the semiring of the weights. Builtin weights include:
b
The classical Booleans:z
The integers coded asint
s:q
The rationals, coded as pairs ofint
s:qmp
The rationals, with support for multiprecision:r
The reals, coded asdouble
s:nmin
The tropical semiring, coded asunsigned int
s:zmin
The tropical semiring, coded asint
s:rmin
The tropical semiring, coded asfloats
s:log
The log semiring, coded asdouble
s: (where denotes .f2
The field: (where denotes the "exclusive or").tupleset
Cartesian product of WeightSets, .
Examples
The usual framework for automaton is to use letters as labels, and Booleans as weights:
If instead of a simple accepter that returns "yes" or "no", you want to compute an integer, work in :
To use words on the usual alphabet as labels:
-tape Automata
To create a "classical" two-tape automaton:
Multiple Weights
To compute a Boolean and an integer:
The following automaton is almost able to recognize : it accepts only words of (aka ) and return . One still has to check that .
Boss
The interpretation of the following monster is left as an exercise for the reader: