A short introduction to Vaucanson

Informations

• Publié par: Bavem
• Nombre de lectures: 14
• Langue: English

Extrait

A short introduction to Vaucanson
March 31, 2004Contents
1 Overview 2
1.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2
1.2 Aim of this document . . . . . . . . . . . . . . . . . . . . . . . . 2
1.3 Installation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3
1.4 Directory tree . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3
1.5 A piece of code . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4
2 Getting started with Vaucanson 5
3 Fundamental: enriched C++ 8
4 Dealing with algebraic structures 10
4.1 Alphabet . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10
4.2 Free monoid . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11
4.3 Semiring . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15
4.4 Series . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 17
4.4.1 Polynoms . . . . . . . . . . . . . . . . . . . . . . . . . . . 17
4.4.2 Rational expression . . . . . . . . . . . . . . . . . . . . . 18
5 Automaton 20
5.1 Instantiating an automaton . . . . . . . . . . . . . . . . . . . . . 20
5.1.1 Structure operations . . . . . . . . . . . . . . . . . . . . . 21
5.1.2 Delta function . . . . . . . . . . . . . . . . . . . . . . . . 21
5.2 Standard services . . . . . . . . . . . . . . . . . . . . . . . . . . . 21
5.3 Standard macros . . . . . . . . . . . . . . . . . . . . . . . . . . . 22
5.4 Usage example . . . . . . . . . . . . . . . . . . . . . . . . . . . . 22
5.4.1 Complete algorithm . . . . . . . . . . . . . . . . . . . . . 22
5.4.2 Implementing new operators . . . . . . . . . . . . . . . . 23
6 Algorithms 26
7 Your ’grep’ 27
1Chapter 1
Overview
1.1 Introduction
Vaucansonisanitestatemachinemanipulationplatform,initiatedbyJacques
Sakarovitch and Sylvain Lombardy in 2001. A nite state machine (also called
automaton) is a computing tool useful in langage processing or automation.
In the past, such platforms were intended to work either at an industrial
scale,specializedinweightedletterautomaton(FSM)tobee cient,orinapure
abstract way (FSA). Using static and generic C++ programming, Vaucanson
tries to respond to these two trends.
Indeed, our framework is the set of automaton with multiplicity over any
semiring: a general algorithm is written just one time and can be statically
instantiatedtoanyparticularkindofautomaton. Asaresult,weobtaine cient
code from algorithms written in an abstract way using basic primitives taken
from the C++ library.
Thus, Vaucanson is:
Generic A general algorithm is written once and is instantiated with the good
parameters at use.
Algorithm oriented The system is meant to provide primitive services to
write algorithms.
Meta The C++ is enriched to obtain a exible framework.
Note that Vaucanson is still a work in progress, since some features have
not yet been heavily tested.
1.2 Aim of this document
The goal of this document is to present the philosophy of the library and to
demonstrate some features of the system in a practical manner.
At the end of this tutorial you should be able to use Vaucanson and write
generic algorithms that works on automata.
2‘-- vaucanson
|-- algebra
| |-- concept
| ‘-- implementation
| |-- alphabets
| |-- free_monoid
| |-- letter
| |-- semiring
| ‘-- series
| ‘-- rat
|-- algorithms
|-- automata
| |-- concept
| ‘-- implementation
|-- config
|-- design_pattern
|-- misc
‘-- tools
Figure 1.1: Vaucanson headers organization.
1.3 Installation
A tarball with Vaucanson’s sources can be found at
http://vaucanson.lrde.epita.fr/Download.
ToinstallVaucanson,uncompressthetarball,thegointothenewlycreated
directory and type:
./configure
make
make install (must be root)
Ifyouarenotrootonyoursystem, youcaninstallVaucansoninyourhome
directory by typing:
./configure --with-prefix=$HOME/vaucanson
make
make install
Theonlydi erenceisthatyoumustspecifythefollowing agsforcompiling:
-I$(HOME)/vaucanson/include.
1.4 Directory tree
The Vaucanson library headers organization is shown in gure 1.1. At the
root of the include directory, the following directories can be found:
algebra De nitions of algebraic structures.
algorithms Generic algorithms provided by Vaucanson.
3*
*
*

*

automata De nitions of automata.
con g The internal con guration system.
design pattern The core of the library which goal is to enrich C++. (see
section 3).
misc SomeusefultoolsfordailyworkwhichareindependentfromVaucanson.
tools Some convenient tools to make Vaucanson easier to use.
1.5 A piece of code
Before looking deeper into the library, listing 1.1 shows a sample piece of code
which should demonstrate how easy it is to write generic algorithms in Vau-
canson.
Listing 1.1: First code sample.
template <class T>
void complete(Element<Automata, T>& a)
{
typedef Element<Automata, T> automaton t;
AUTOMATONTYPES(automaton t);
const alphabet t& alphabet = a. series () .monoid() .
alphabet() ;
std :: set<hedge t> delta ret ;
hstate t hole state = a. add state() ;
for each state(s , a)
for each letter (e , alphabet)
{
delta ret . clear () ;
a. letter deltac (delta ret , s , e);
if ( delta ret . size () == 0)
a. add letter edge( s , hole state , e);
}
}
4





Chapter 2
Getting started with
Vaucanson
This section is meant to show how to write a program using the Vaucanson
library. The aim of this example is to build an automaton from a rational
expression, and then to evaluate the series denoted by the automaton on a
given word.
In order to understand everything, you will be shown step by step how to
write this program.
First, we need to include several les for our program to work.
#include <vaucanson/r automaton.hh>
#include <vaucanson/algebra/implementation/series/krat .
hh>
#include <vaucanson/algebra/implementation/series/
krat exp parser .hh>
#include <vaucanson/algorithms/standard of .hh>
#include <vaucanson/algorithms/eval .hh>
#include <iostream>
#include <string>
vcsn::r_automaton::automaton_t is the type of automaton we will be
working on. It is de ned in the le r_automaton.hh.
The macro AUTOMATON_TYPES_EXACT is used to get typedefs on all the alge-
braic types we need to build our automaton.
int main()
{
AUTOMATONTYPESEXACT(vcsn :: r automaton :: automaton t)
;
Thetwofollowing typedefaresugartomakeyourcodeeasiertounderstand
later on. exp_t is our rational expression implementation, and krat_t our
5



element of series implemented with rational expressions.
typedef vcsn :: rat ::exp<monoid elt value t ,
semiring elt value t > exp t ;
typedef vcsn :: Element<series t , exp t> krat t ;
The next step is to declare an alphabet, and to insert all the ascii characters
in it.
alphabet t alpha;
for (int l = 0; l < 256; ++l)
alpha. insert(l);
monoid is the free monoid associated to the alphabet alpha, and semiring
the semiring to work with.
monoid t monoid (alpha);
semiring t semiring ;
series_set is the set of series associated to the monoid and semiring we
are working with.
series t series set (semiring , monoid);
automata is the set of automata associated to the set of series series_set.
automata set t automata ( series set );
The next step is to read the rational expression from the standard input and
put it in a std::string.
char chr rx [1024];
std :: cout << ”Type in your rational expression : ” <<
std :: endl ;
std :: cin . getline(chr rx , 1024) ;
std :: string str rx ( chr rx);
The string we have needs to be parsed in order to retrieve the rational ex-
pression. That is why we declare a krat_t variable and call the parse function.
rx is an element of the set of series series_set. If the parsing fails, the parse
function returns (true, error_message), (false, X) otherwise.
krat t rx ( series set );
std :: pair<bool , std :: string > r = parse(str rx , rx);
if (r. first )
{
std :: cerr << ”Error: ” << r.second << std :: endl ;
return 1;
}
6