previousnext
ASTL homeSTL home
DFA_bin


Implements

 DFA

Class Specifications
name DFA_bin
template parameters class _Sigma = Type_alphabet<char>,
class _Tag = empty_tag,
class Allocator = default_allocator
constructor DFA_bin(unsigned long = 0, Allocator a = Allocator())

File

 dfa_bin.h

Structure

 This is one of the three arrays DFA. In thes representation, we store the outgoing transitions of a state in an array of couples in Sigma*Q. they are to be used when space memory constraints are strong since they are the least consumming structures.
Each state is a pair of tag and STL vector storing couples in Sigma*Q. The sort key is Sigma and transition retrieval is carried out by a binary search. F is a bit vector.

time

 Add/remove state: O(1)
Add/Remove transition: O(c+log2(c))
Access transition: O(log2(c))
Iteration on edges:O(c)

Space

Use Cases

 This class is part of the three arrays classes. It is usefull when memory space is limited and when side effects opértions are scarce, since adding a transition is in linear time.