Welcome to this Vcsn tutorial. Vcsn is a platform (C++ libraries with various interfaces, a Python binding, and some specific features for IPython) for weighted automata and rational expressions.
This (too) short tutorial guides you through the Python binding of Vcsn, and more specifically the IPython interface. If you are not a Python programmer, rest assured that there is not much to know, and if you are a Python programmer, rest assured that its conventions have been respected, and you will be able to take the full benefit from both Vcsn and Python.
Once you read this page, you should explore these:
Vcsn offers several interfaces:
static
dyn
on top of static
dyn
TAF-Kit
.This documentation shows how to use the IPython interactive environment. Provided that Vcsn was properly deployed on your platform, to launch it run the following command from your shell:
$ vcsn notebook &
A web browser should open on a list of files. Click on the "New" menu, and select "Python" (or "Python 3"), which should open a new sheet. The remainder of this documentation is about such sheets.
First, import Vcsn into Python, and define the "context" in which you want to work. Do not worry about the (ugly!) syntax, just see where the alphabet (the set of letters, $\{a, b, c\}$) is defined. The last line (ctx
) is here so that IPython displays what this variable contains.
In [1]:
import vcsn
ctx = vcsn.context("lal_char(abc), b")
ctx
Out[1]:
This object, the context, defines the types of the various entities. To build a rational expression on this alphabet, use ctx.expression
as follows:
In [2]:
r1 = ctx.expression("ab*")
r1
Out[2]:
The syntax for rational expressions is as follows (with increasing precedence):
\z
denotes the empty language\e
denotes the language of the empty worda
denotes the language of the word a
e+f
denotes the union of the languages of e
and f
(note the use of +
, |
is not accepted)ef
denotes the concatenation of the languages of e
and f
e*
denotes the Kleene closure of the language of e
For more details, please see the documentation of expressions.
So for instance r1
denotes the words starting with a single a
followed by any number of b
s.
Rational expressions are objects that feature methods. One such method is shortest(
number
)
that lists the number
first (in shortlex order) words of the language defined by the rational expresion:
In [3]:
r1.shortest(10)
Out[3]:
You may compose rational expressions using Python operators such as +
for sum, *
for multiplication (concatenation):
In [4]:
r1 + r1 * r1
Out[4]:
Vcsn features different means to build an automaton from a rational expression. The expression.standard()
method builds the "standard autamaton", also known as the "position automaton", or the "Glushkov automaton":
In [5]:
r1.standard()
Out[5]:
When it comes to displaying automata as graphs, there are several "traditions". In Vcsn, initial states are denoted by an entering arrow, and final (or "accepting") states by an exiting arrow. This automaton has one initial state, and two final states.
The expression.derived_term()
method builds the "derived-term automaton", aka, the Antimirov automaton.
In [6]:
a1 = r1.derived_term()
a1
Out[6]:
Python operators that are accepted by rational expressions are also accepted by automata, with matching semantics.
In [7]:
a2 = (r1 + r1*r1).derived_term()
a2
Out[7]:
In [8]:
a3 = a1 + a1 * a1
a3
Out[8]:
Well, those two automata are not equal (or more rigorously "isomorphic"), but they are equivalent:
In [9]:
a2.is_equivalent(a3)
Out[9]:
All the classical algorithms about automata are implemented:
In [10]:
a3
Out[10]:
In [11]:
a3.determinize()
Out[11]:
The states of this automaton are decorated with metadata: the corresponding set of states of the input automaton. Use strip
to remove this decoration.
In [12]:
a3.determinize().strip().complete()
Out[12]:
Note that useless states and transitions are gray.
To evaluate a word on an automaton, use eval()
, or simpler yet: use the automaton as if it were a function:
In [13]:
a3.eval("a")
Out[13]:
In [14]:
a3("b")
Out[14]:
To see the 10 first accepted words (if there are that many), use shortest(10)
:
In [15]:
a3.shortest(10)
Out[15]:
To extract a rational expression from the automaton, use expression()
:
In [16]:
a3.expression()
Out[16]:
This concludes this quick overview of Vcsn's IPython interface. You should now proceed to discover other features in other notebooks.