3.1. Finite State Machines

Models of computation

---

In order to know what is computable (and what is not computable) we need to have a clear model of computation. It seems reasonable to start with a very simple model.

The model discussed here is very weak. We ask, what can be computed if you have a fixed, finite amount of memory, but must nonetheless be able to solve problems whose inputs are arbitrarily large?

Basics

---

Chapter 2 of Sipser describes finite state machines, which he calls DFAs. (DFA stands for deterministic finite automaton.) I will try to match Sipser's terminology, so I will also call them DFAs. The discussion of DFAs here is intended only to be a sketch. Sipser provides far more detail.

A DFA solves a language problem. Its input is a string and it answers yes or no to the question, is the input in this language?

The alphabet of a DFA

Suppose that we want to make a DFA to solve a particular problem. That problem should have an alpabet in which inputs can be written, which is also the alpabet of the DFA.

States

A DFA has a finite set of states. One of those states is designated as a start state. Every state is designated either as an accepting state or as a rejecting state.

Transitions

For each state q and symbol c in the alphabet, there is another state q' = δ(q, c). We say that there is a transition from q to q' on symbol c.

Finite state diagrams

It is easiest to understand a finite state machine in a diagramatic form. Here is an example with alphabet {a, b}. (I apologize for the ASCII art, but I do not have time to produce better graphics.)

Let's call this example M₁.

            |
            v
          _____    b    _____
      ___|     |------>|     |___
   a |   |  0  |       |  1  |   | b
     `-->| (y) |<------| (n) |<--'
         |_____|   a   |_____|

State 0 is an accepting state (marked (y) for yes) and state 1 is a rejecting state (marked (n) for no). (Sipser uses a single circle around a state for a rejecting state and a double circle for an accepting state.)

The start state is state 0 (indicated by the arrow pointing to state 0.) The transitions are:

δ(0, a) = 0
δ(0, b) = 1
δ(1, a) = 0
δ(1, b) = 1

The idea is to read an input and follow a transition for each symbol. Suppose that the input is abba. M₁ starts in state 0. When the first a is read, it goes stays in state 0. It goes through the following chain of states.

        a       b      b      a
    0  --->  0 ---> 1 ---> 1 ---> 0

Since it ends in state 0 and state 0 is an accepting state, we say that M₁ accepts string abba. On input bab, M₁ goes through state sequence

       b      a      b
    0 ---> 1 ---> 0 ---> 1

Since the last state is a rejecting state, we say that M₁ rejects string bab.

It should be clear that M₁ accepts all strings that end on a and rejects all that end on b. So the language accepted by M₁ (written L(M₁)) is

L(M₁) = {x | x ∈ {a,b}*, x ends on a}

A careful definition of a finite state machine

---

A finite state machine M consists of 5 things: An alphabet A, a set of states Q, a start state q₀ ∈ Q, a subset F of Q whose members are the accepting states, and a function δ: Q×A → Q.

We define another function δ*: Q×A* → Q so that δ*(q,s) is the state on which M stops when it reads string s, starting in state q. The definition of δ* is as follows.

δ*(q, ε) = q
δ*(q, sc) = δ(δ*(q, s), c)

where both equations hold for every state q and the second equation holds for all strings s ∈ A* and symbols c ∈ A.

The language that M accepts is L(M) defined by

L(M) = {s | s ∈ A*, δ*(q₀, s) ∈ F}.

That is, M accepts all strings take M to an accepting state when M starts in state q₀.

Understanding states

---

Here is another example of a DFA, M₂. This one has alphabet {0,1} and states {0,1,2}.

           |
           v
          ___    1    ___    0    ___
      ___|   |------>|   |------>|   |___
   0 |   | 0 |       | 1 |       | 2 |   | 1
     `-->| y |<------| n |<------| n |<--'
         |___|   1   |___|   0   |___|

DFA M₂ has only 3 states. That means it can only remember one of 3 possible pieces of information about the input that it has read at any point.

A claim about M₂

Think of the input s of M₂ as a binary number, and let N_s be the number that s stands for. For example,

N₁₁₀ = 6

Claim. If δ*(0, s) = i then

N_s mod 3 = i,

for i = 1, 2, 3.

That is, what M₂ remembers is the input mod 3. Since state 0 is the only accepting state,

L(M₂) = {s | s is a binary number that is divisible by 3}.

Proof of the claim

The claim is based on the following facts.

1. If x is a binary number, then

   x0 represents 2x,
   x1 represents 2x + 1.

   For example, 110 represents 6. 1100 represents 12 = 2(6) and 1101 reprents 13 = 2(6) + 1.

2. For any integer x, if x mod 3 = y then

   (2x) mod 3 = (2y) mod 3,
   (2x+1) mod 3 = (2y+1) mod 3.

3. 2(0) mod 3 = 0
   2(1) mod 3 = 2
   2(2) mod 3 = 1
   
   (2(0) + 1) mod 3 = 1
   (2(1) + 1) mod 3 = 0
   (2(2) + 1) mod 3 = 2

When M₂ moves from state a to state b on a 0, it is always true that b = (2a) mod 3.

When M₂ moves from state a to state b on a 1, it is always the case that b = (2a+1) mod 3.

The machine starts in state 0 = 0 mod 3.

So, after reading the bits of binary number x, M₂ is in state x mod 3. ◊