ASTL homeSTL home

Non-deterministic Finite Automaton


This is the automaton, as described by the concept file, without additionnal restriction...You are allowed as many initial states as you want, and you can go to multiple states from one using the same label
Since it's an abstract type, you can only use it throught one of its implementations.

Model of


Exported types

Those are exactly the same as defined in automaton.

public members

Those have already been defined in automaton, they are reprinted here with their exacts arguments and return types for NFA
name return and arguments description
null_state State ...
begin const_iterator () return an iterator on the first state of the automaton
end const_iterator () return a past the end iterator on the automaton
new_state State () return a handler on a freshly allocated state
new_state T (unsigned long n, T x) With T being an output iterator, returns x with n handlers on newly allocated states
del_state void (State) remove the corresponding referenced state
copy_state void (State from, State to) overwrite state from with state to
duplicate_state State (State q) copies q into a newly allocated State
(as would copy_state(q, new_state()))
state_count unsigned long () returns current number of states
set_trans void (State s, const Alphabet& l, State aim) adds a transition between states s and aim, labelled by l
del_trans void (State s, const Alphabet& l) removes the transitions by l from state s
del_trans void (State s, const Alphabet& l, State aim) removes the transition to state aim by l from state s
change_trans void (State s, const Alphabet& l, State former_aim, State new_aim) ensures that the transition of s previously leading to former_aim labelled by l now leads to new_aim
delta1 T (State s, const Alphabet& l,T x) with T being an output iterator, returns an iterator on all states reachable from s by l
delta2 Edges (State s) returns the set of all outgoing transitions of s
trans_count unsigned long returns the current number of outgoing transitions
initial void (State s) set s as an initial state
initial const vector<State>& () returns the initials states, null_state if undefined
final bool (T first, T last) T being an intput iterator, returns wether or not one of the state referenced between first and last is final
final set_F::reference (State s) returns a reference on the finality of s
tag Tag& (State s) returns a reference on the tag of state s

DFA implementations

ASTL currently provides two NFA classes. Those classes are:
  1. NFA_matrix:
  2. DFA_mmap: