**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})**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, where*(Q,Σ,δ,s,W)**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}) **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