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.