previousnext
ASTL homeSTL home
NFA matrix


Implements

NFA

Class Specifications

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

File

nfa_matrix.h

Structure

A 3D matrix. We associate to each state a vector of state vectors: one state vector for each alphabet letter. F is a bit vector.

time

Add state:
Remove state:
Add transitions:amortized O(1)
Remove transition:O(|(q,a)|)
Access transition:O(1)
Iteration on edges:

Space

+Qt

Use Cases

same as DFA_matrix, but for a NFA