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:

  1. The set of states Q. In the example illustrated above, Q = {a, b}.
  2. The set of symbols S that can appear in the input string (this is sometimes called the alphabet).
  3. 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.

  4. The initial state of M.
  5. 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:
  1. Initially, before any of the input has been consumed, the state is the start state of the finite state machine.

  2. At any point in the simulation, suppose that the finite state machine is in a state q1. We have the following possibilities:
    1. 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.
    2. Not all of the input has been consumed. Suppose that the next input symbol is a. We have the following possibilities:
      1. 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.
      2. There is no transition from state q1 to state q2 on symbol a. In this case the input is rejected.