We recall here our definition of an automaton :
We aim to design code with efficiency and genericity in mind, thus we add to
the usual abstract type automaton two sets T and in order to associate
any kind of information (tags) to the states.
Let be a 7-uple of finite sets defined as
follow :
the alphabet
Q
a set of states
a set of initial states
a set of final states
a set of transitions
T
a set of tags
a relation between states and tags
Let be the context of a state : , that is the set
of the letters on the outgoing edges of a state q.
We define P(X) as the power-set of a set X and |X| as its number of
elements.
Let's view as two distinct transition functions and
according to the most frequent operations needed on an automaton:
These two functions are the corner
stone of the library. To put it formally, everything comes down to manipulate a
set of triples in and two subsets of Q.
Besides these definitions, we introduce the notion of occupation ratio
defined as follow:
and the average
value, as :
This value
is crucial in estimating which container fits better when memory space is
limited. Intuitively, the closer gets to 0, the emptier
the transition matrix will be.
Next:Structure of the Library Up:Generic programming on automata Previous:IntroductionVincent Lemaout 12/9/1997