next up previous
Next: Adjacency list by maps Up: Automaton Representations Previous: Automaton Representations

Matrix

It is the most natural way to implement the set of transitions. It makes use of a $(Q \times \Sigma)$ matrix providing constant time access and easy iteration on Q. On the other hand, this container demands $O(\vert\Sigma\vert \times
\vert Q\vert)$ memory space, which is inefficient for example in natural language processing where $\vert\Sigma\vert$ 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