Sequences and Automata
Automata or finite state machines can typically be thought of as directed graphs, with edges labeled using some specific alphabet, Σ. Most familiar types of automata transition from state to state by reading input letters from Σ, following edges with matching labels; the ordered input for such an automaton forms a sequence called a word (or input word). The sequence of states encountered by the automaton when processing a word is called a run. A nondeterministic automaton may have unlabeled or duplicate out-edges for any state, giving more than one successor for some input letter. This is typically thought of as producing multiple possible runs for a given word, each being a sequence of single states, rather than producing a single run that is a sequence of sets of states; however, 'run' is occasionally used to mean the latter.
Read more about this topic: Sequence