Next: Adjacency list by maps
Up: Automaton Representations
Previous: Automaton Representations
It is the most natural way to implement the set of transitions. It makes use of
a
matrix providing constant time access and easy iteration
on Q. On the other hand, this container demands
memory space, which is inefficient for example in natural language
processing where
and |Q| can be very large and the
matrix nearly empty as the graph is not complete. Moreover, we need an
assumption on the number of states right from the start for a state insertion
is linear in the size of Q.
Vincent Lemaout
12/9/1997