A finite state machine models or programs a system as a finite set of states with transitions between them. The transitions are often labelled by some sort of action or terms. Examples of the user of finite state machines include in robotic systems or software agents to respond to events, and in natural language processing to represent aspects of grammar. Based on the latter, some forms of pattern matching including regular expressions are complied into finite state machines for efficient execution.
A four state finite state machine that encodes the reguar expression {(A|B|C)*}
| S0 => | # at least one A at start |
| S1 => | # anything |
| S2 => | # B followed by B or A |
| S3 => | # C followed by C or A |