In what follows, we'll be continue developing enough knowledge of
sets and functions to describe the following machine M1:
δ: 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:
If I really want to represent an automaton as a sequence of characters, I can reduce this table by, 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 labeled by the elements of the alphabet in the order the alphabet is given to us and that the rows of are labeled 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.
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.
|  | |||
|  | |||
|  |
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:
|