Finite State Machines
Background
A finite state machine (also called a finite state automaton) is an
abstract computational device that has a finite number of different
states that it can be in. Starting in a special state called
the initial state (or the start state), it reads in a sequence
of input symbols and moves from one state to another, based on the input
symbols it sees. (The specific kind of finite state machine
we'll be concerned with in this assignment are sometimes called
deterministic finite state machines. This means that for each state
in the finite state machine, for each symbol that could appear in an input string,
there is at most one outgoing transition for that symbol.)
If it is able to ``consume'' all of the input sequence and
end up in one of a special set of states called accepting states
(also called final states), it accepts the input; otherwise,
the input is rejected. In general, a finite state machine has
exactly one start state, but may have zero, one, or many final states.
Finite automata are used to model a wide
variety of real-life devices, from traffic lights to network communication
protocols.
Pictorially, a finite automaton is often depicted using circles to denote
states and arrows between circles to denote transitions between states.
For example, the following depicts a finite state machine that accepts bit
sequences containing an odd number of 1s.
The state transitions occurring in this automaton, given the input
10011, are as follows:
Since the finite automaton is in a final state (state b) when it
reaches the end of its input string, the input 10011
is accepted. On the other
hand, given the input string 1001, the automaton ends up in
state a when the end of the input string is reached, and since
a is not a final state, the string 1001 is not
accepted by the automaton (even though the automaton goes through the
final state b along the way while processing the input string).
Specifying a Finite State Machine
To specify a finite state machine M completely, we must specify the following:
-
The set of states Q. In the example illustrated above,
Q = {a, b}.
-
The set of symbols S that can appear in the input string
(this is sometimes called the alphabet).
-
The state transitions of M. Each transition
is specified by the state from which the transition is made, the state to
which it is made, and the alphabet symbol on which that transition
is made.
In the finite state machine illustrated above, these transitions
are indicated by arrows, each arrow labelled with the alphabet symbol
on which the transition occurs. This set of transitions includes (among
others): a transition from a to a on symbol 0; and a
transition from a to b on symbol 1.
-
The initial state of M.
-
The set of final states F. In the example above, F = {b}.
Simulating a Finite State Machine
Simulating a deterministic finite state machine involves keeping track of
the current state of the finite state machine as the input is processed:
-
Initially, before any of the input has been consumed, the state is
the start state of the finite state machine.
-
At any point in the simulation, suppose that the finite state machine
is in a state q1. We have the following possibilities:
-
All the symbols in the input have been consumed. In this case, if
state q1 is a final state, the input is accepted,
otherwise it is rejected.
-
Not all of the input has been consumed. Suppose that the next input symbol
is a. We have the following possibilities:
-
There is a transition from state q1 to state q2 on
symbol a. In this case, the next input symbol
(which, as stated, is a) is consumed and the current state
becomes q2.
-
There is no transition from state q1 to state q2 on
symbol a. In this case the input is rejected.