previousnext
ASTL homeSTL home

Automaton

description

An automata could be defined as an object that stores words. It is a set of states, which can store informations in tags, and transitions, which are labelled with element of a Sigma, linking states together. The two most basic informations about states are their finality (ie:inital and/or final, or none), a valid word being defined by the path between an initial and a final state.
ASTL automata only provide support for the most basic operations, all algorithms being implemented outside the automaton classes, thus alllowing maximum flexibility.

Schema: the abstract automaton

refines

None, but this is a concept parallel to container

associated types

type identity description
Sigma X::Sigma The user defined type Sigma, set of the transitions possible labels
Alphabet X::Alphabet also X::Sigma::Alphabet, the user defined type used for transitions labels (ie:type of the Sigma elements)
State X::State A type used to reference a state (a handler). this is a built in type.
StateData X::StateData type of the state (its contents)
Const iterator X::const_iterator forward iterator on the automaton states, read only.
Edges X::Edges a key-associative container holding the outgoing transitions of a state.
Tag X::Tag type of the objects holding data associated with a state (such things as being final, before ASTL 1.1, now only used for user defined tags)


notations

A is a model of automaton
a an object of type A
l an object of type A::Alphabet
from, to objects of type A::State

definitions

let be the 7-uple of sets representing the automaton, with
the alphabet
Q a set of states
IQ a set of initial states
FQ a set of final (accepting) states
Q xx Q a set of final (accepting) states
T a set of tags
Q x T a relation between states and tags

c(q) is the context of a state, that is: the set of letters on the outgoing transitions of a state q.
We call restricted context, rc(q,l) the set of all aims of a state q by a letter l.
We write P(X) for the power-set of a set X and |X| for its number of elements. Let us view astwo distinct transition functions and according to the most frequent operations needed on an automaton.


Theses two functions are the corner stone of the library. To put it formally, everithing comes down to manipulate a set of triples in QxxQ and two subsets of Q.

valid expressions

name expression type requirement return type
Null state a.null_state ... this is a State
Beginning of states set a.begin() ... const_iterator
End of states set a.end() ... const_iterator
creating a new state a.new_state() ... State (handler on the newly created state)
deleting a state a.del_state(s) ... ...
copying a state into an other a.copy_state(from, to) ... ...
duplicating a state a.duplicate_state(from) ... State (handler on the newly created state)
number of states a.state_count() ... returns an unsigned long
setting a transition between two states a.set_trans(from,l,two) ... ...
deleting a transition a.del_trans(from,l) ... ...
modyfing the aim of a transition a.change_trans(...) ... ...
a.delta1(from, l) ... ...
a.delta2(from) ... Edge
number of transitions a.trans_count() ... unsigned long
get initials states a.initial() ... ...
set an initial state a.initial(from) ... ...
get finality a.final(from) const bool
get a finality reference a.final(from) ... ...
tag a.tag(from) ... Tag&


Expression semantics

name expression precondition semantics postconditions
Null state a.null_state ... State equivalent of NULL ...
Beginning of states set a.begin() ... returns a const_iterator pointing to the first state in the automaton past the end if no states
End of states set a.end() ... returns a const_iterator pointing one past the last state in the automaton past the end
creating a new state a.new_state() the automaton must be editable allocates a new state ...
deleting a state a.del_state(from) the automaton must be editable desallocates the state referenced by from ...
copying a state into an other a.copy_state(from, to) the automaton must be editable copies the content of from in to ...
duplicating a state a.duplicate_state(from) the automaton must be editable copies from into a newly allocated state ...
number of states a.state_count() ... returns the current number of states of this automaton ...
setting a transition between two states a.set_trans(from,l,two) the automaton must be editable adds a transition by l from from to to ...
deleting a transition a.del_trans(...) the automaton must be editable removes a transition ...
modyfing the aim of a transition a.change_trans(...) ... changes the aim of a transition ...
a.delta1(from, l) ... returns the states reachable from from by l returns null_state if the transition does not exist
a.delta2(from) ... returns the set of all outgoing transitions of state from ...
number of transitions a.trans_count() ... returns the current number of transitions of this automaton ...
get initials states a.initial() ... returns I null_state if none
set an initial state a.initial(from) ... sets from as an initial state ...
get finality a.final(from) s is a const returns the finality of from ...
get a finality reference a.final(from) ... returns a reference on the finality of from, thus allowing modification ...
tag a.tag(from) ... return the Tag associated with state from ...

complexity garantees

implementation dependant...

invariants


abstracts models


about DFA and NFA

While all automata handle the same kind of operations (adding and removing states, setting transitions,...) their is some diferences depending on wether you assume that, from a given state and by a given label, you can reach one or more state. Technically: wether you are using a deterministic or a non deterministic automaton. So to better fullfill the user need, the ASTL automata classes have seemingly been divided beetween Deterministic Finite Automaton and Non-deterministic Finite Automaton.

Main differences between NFA and DFA:

DFA
NFA
I one reference on one Initial state sequential container of state reference
Edges a unique-key associative container a multiple-key associative container