If you ever took an automata theory course in Computer Science, you have come across state machines. A deterministic finite state automata (FSA) is usually defined as follows:
where S is a finite set of states; 
, the set of initial states, is restricted to be a
singleton set; 
is a finite set of final states; A is a
finite set of actions, and 
is a deterministic function.
| FSA terminology | State Machine terminology |
| alphabet | actions |
| string | trace  |
| language L(M) | behavior Beh(M) |
Here ``trace '' means the trace of an execution ending in a final
state.
Sometimes the language of M is called regular or a regular set
because it can be expressed as a regular expression using 
,
and concatenation. Just as with the behavior of a machine, the
language of an FSA
can be infinite, i.e., there might be an infinite
number of strings accepted
by M.