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 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.
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.
|  | |||
|  | |||
|  |
#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;
}