... A Formal Definition
page 2
The components of an description
Earlier, we identified the main components of a finite state automaton that we could abstract from our informal study of real finite state machines. We can repeat these here:
 | They have a finite number of memory states. |
| One of the memory states is designated to be the start state, the state in which the machine always first starts |
| Some of the memory states are selected to be goal states, or end states. |
| Each input to the machine by the user causes the machine to change states from the current memory state to the next memory state (possibly the same state as the current state) based on what the input is. |
| The set of inputs is well specified. For example, if a dispensing machine takes coins, it only takes certain kinds, such as US nickels, dimes, and quarters. This set of inputs is also finite. |
| The sequence of inputs is finite. For example, if someone is using a candy bar dispenser, he or she will only input a finite number of coins. |
We can capture the essential characteristics here in a mathematical definition.
The components of a formal definition
S: the finite set of states
We can let S stand for the set of states in a finite state automaton. Why S? It is just notation, so we can use anything we want. Using "S" should remind us of "states," which makes it a reasonable choice. The states correspond to the circles we draw in our finite state automaton diagrams.
I: the finite set of input symbols
We chose I for the input set for the same reason that we chose S for the set of states: "I" reminds us of "input." This is the set of symbols that can be input, one at a time, to the finite state automaton. In a real automaton, the input "symbols" might be nickels, dimes, and quarters, but in the abstract sense, we will just use single letters, such as a, b, c, and so forth, to stand for input symbols. The input symbol set contains the values used as labels in our finite state automaton dieagrams.
t: the transition function
Here, we use t to stand for the transition function. The transition function is just the description of what the next state is given the current state and input symbol. For example, if the automaton is in state s1 and the input symbol is a, then t(s1,a) = s5 means that the next state to enter from s1 given a is s5. In other words, the transition function describes how the automaton behaves as it processes inputs. In our finite state automaton diagrams, the transition function is represented by all of the arrows.
s0: the start state
Given a set of states, we must designate one as the start state. For uniformity, we will just call this state s0 generically. Every finite state automaton is expected to have exactly one start state. In our diagrams, the start state is the one marked with the > symbol.
A: the set of accepting states
Given the set of states, we must also designate some to be accepting states. Interestingly, we don't have to have any accepting states (the set of accepting states can be empty), but most interesting finite state automata will have some accepting states. In our finite state automaton diagrams, this set corresponds to the states drawn with double circles.
A Formal Definition
Here then is a formal definition of a finite state automaton:
Definition
A finite state automaton is a five-component system,
M = (S, I, t, s0, A)
where S is a finite set of states, I is a finite set of input symbols, t is the transition function, s0 is the start state, and A is the set of accept states.
