Reading
Sections 2.1 of Theory of Computing, A Gentle Introduction. Now we can finally understand their definition of a Deterministic Finite Automaton.
Homework
Printout the homework and answer the questions on that paper.

In what follows, we'll be continue developing enough knowledge of sets and functions to describe the following machine M1:

Functions
So how are we going to represent the transitions in a finite automaton? Well, essentially what you're asking is this: "if I'm in state q and I read character x, what state should I go to?" In other words we want to be able to give a state and a character as input and get a state as output. Hopefully this sounds like a function to you! If Q is the set of states in your machine and Σ is the alphabet, the domain of the function (i.e. the set of possible input values) is Q x Σ (i.e. all pairs whose first component is a state and whose second component is a character). The range of the function (i.e. the set of possible output values) is Q. For our example machine M1, the domain is {(q0,a),(q0,b),(q1,a),(q1,b),(q2,a),(q2,b)}. By convention, this transition function is named δ. The proper mathematical way to indicate the domain and range of a function is to give the domain "→" the range. So for δ we have:

δ: Q x Σ → Q

This plays precisely the same role as a prototype in C++. It tells you what the possible inputs are and what the possible outputs are.

Now for the sake of writing out the 5-tuple representing a machine in as legible a form as possible, I provide a table defining the function δ rather than truly reducing it to a sequence of symbols. This gives us the following definition of M1:

\[ M1 = \left( \underbrace{\{q_0,q_1,q_2\}}_{\text{states}}, \underbrace{\{a,b\}}_{\text{alphabet}}, \underbrace{ \begin{array}{c|cc} & a & b\\ \hline q_0 & q_2 & q_1\\ q_1 & q_2 & q_1\\ q_2 & q_1 & q_2 \end{array} }_{\text{transitions}}, \underbrace{q_0}_{\text{start state}}, \underbrace{\{q_0,q_2\}}_{\text{accepting states}} \right) \] A 5-tuple representing M1

If I really want to represent an automaton as a sequence of characters, I can reduce this table to, for example, listing its rows. Thus, the table becomes ((q2,q1),(q2,q1),(q1,q2)). Now the complete specification of M1 as a set of symbols becomes:

M1 = ({q0,q1,q2},{a,b},((q2,q1),(q2,q1),(q1,q2)),q0,{q0,q2})
The assumption here is that table is given to us with the columns labelled by the elements of the alphabet in the order the alphabet is given to us and that the rows of are labelled by the elements of the set of states in the order given to us. There are other ways to describe the transition function as a string of symbols that don't rely on order this way.

The payoff: a formal definition of a finite automaton
Here we've been putting a lot of work into getting a representation of a finite automaton as a string of characters, but it turns out we get something more - a formal mathematical definition of what a finite automaton is! (Technically a deterministic finite automaton, we'll look at non-deterministic finite automata later.)

A deterministic finite automaton is a 5-tuple (Q,Σ,δ,s,W), where
  • Q is the set of states (must be finite!)
  • Σ is the alphabet (must be finite!)
  • δ is a function, δ: Q x Σ → Q, defining the transitions
  • s is the start state, s ∈ Q
  • W is the set of accepting states, W ⊆ Q

Anything satisfying the requirements of this definition is a finite automaton. With a formal definition like this, we'll be able to give formal proofs (which will generally be algorithms) about properties of finite automata.

Lots of examples!
Here are several examples of machines given as diagrams versus machines given formally as 5-tuples:
({q0,q1},{i,j,k},
  | i  j  k 
--+---------
q0| q1 q0 q0
q1| q0 q1 q1
,q0,{q1})
({q0,q1,q2},{a,b,c},
  | a  b  c 
--+---------
q0| q1 q0 q0
q1| q1 q0 q2
q2| q2 q2 q2
,q0,{q1,q2})
({q0,q1,q2,q3,q4},{a,b},
  | a  b 
--+------
q0| q1 q3
q1| q1 q2
q2| q2 q2
q3| q4 q2
q4| q2 q4
,q0,{q1,q4})
You're going to need to get comfortable with moving back and forth between the mathematical specification of a machine as a 5-tuple and the diagram of a machine.

Simulating finite automata in programs
Now that we see transitions as merely being applications of a function call, we could think of writing programs that implement finite automata. For example, what about defining a C++ class that models the workings of the finite automaton M1. That class definition is given below, along with a simple program that demonstrates the class in action. (Below that is a better implementation.)
#include <iostream>
#include <cstdlib>
using  namespace std;

/**********************************************************
 * This class simulates the working of the machine:
 *                      | a   b
 *                    --+------
 * ({q0,q1,q2},{a,b}, q0| q2 q1 ,q0,{q0,q2})
 *                    q1| q2 q1
 *                    q2| q1 q2
 **********************************************************/
class Machine
{
private:
  int state;
public:
  Machine() { state = 0; }
  void read(char c)
  {
    if      (state == 0 && c == 'a') state = 2;
    else if (state == 0 && c == 'b') state = 1;
    else if (state == 1 && c == 'a') state = 2;
    else if (state == 1 && c == 'b') state = 1;
    else if (state == 2 && c == 'a') state = 1;
    else if (state == 2 && c == 'b') state = 2;
    else {
      cerr << "Symbol " << c << " not in alphabet!" << endl;
      exit(1); 
    }    
  }
  bool isaccept() { return state == 0 || state == 2; }
};

/**********************************************************
 * This main provides a simple driver for testing the class
 * Machine.
 **********************************************************/
int main()
{
  Machine M;
  for(char c = cin.get(); c != '\n'; c = cin.get())
    M.read(c);
  cout << (M.isaccept() ? "accept" : "reject") << endl;
  return 0;
}

Notice how easy it is to translate a machine specification into code. As the challenge part of the homework points out, this could even be done automatically - i.e. a machine specification could be automatically transformed into a program.

Performance-wise, the above code is a disaster. A single transition might take as many as |Σ||Q| steps --- i.e. we check each character/state combination. If we give each alphabet symbol an index, we can represent the transition function δ as a table (i.e. a 2D array), just like we do when writing out 5-tuples for machines. That way, each transition is done in a single step. Similarly, in the above code, determining whether we're in an accepting state can take as many as |W| steps. Once again, clever use of arrays can make that constant time. Here's that code:

#include <iostream>
#include <cstdlib>
using  namespace std;

/**********************************************************
 * This class simulates the working of the machine:
 *                      | a   b
 *                    --+------
 * ({q0,q1,q2},{a,b}, q0| q2 q1 ,q0,{q0,q2})
 *                    q1| q2 q1
 *                    q2| q1 q2
 *
 * This version of the program uses a 2D array of ints to
 * represent the transitions.  Thus, each transition is a
 * table lookup, and only takes O(1) time.
 **********************************************************/
const int delta[3][2] = {{2, 1},{2, 1},{1, 2}};
const bool W[3] = {true,false,true};
class Machine
{
private:
  int state;
public:
  Machine() { state = 0; }
  void read(char c)
  {
    if (c < 'a' || c > 'b') {
      cerr << "Symbol " << c << " not in alphabet!" << endl;
      exit(1); }
    int symID = c - 'a';
    state = delta[state][symID];
  }
  bool isaccept() { return W[state];}
};

/**********************************************************
 * This main provides a simple driver for testing the class
 * Machine.
 **********************************************************/
int main()
{
  Machine M;
  for(char c = cin.get(); c != '\n'; c = cin.get())
    M.read(c);
  cout << (M.isaccept() ? "accept" : "reject") << endl;
  return 0;
}


Christopher W Brown
Last modified: Wed Sep 2 09:44:27 EDT 2009