Return to the C++ Demos Home Page
Finite Automata
Borland Turbo C++ was used
This code emulates a simple Turing machine.
The Header
#include <iostream.h>
#include <conio.h>
class TuringMachine
{
protected:
char* Tape;
char* HeadString;
// The Quad Variables
int* Starts;
char* Readins;
char* Actions;
int* Finis;
// Other Fun Stuff
int Head,TapeMax,StartingPoint,NumQuads;
public:
TuringMachine(int InitTapeMax);
void SetInput(int Input1,int Input2=0);
void ShowTape(int InX, int InY);
void InitTape();
void MoveRight();
void MoveLeft();
void WriteSymbol(char Sym);
void InitHead();
void ShowHead();
int GetStart() { return StartingPoint; }
void SetHead(int InitHead) { Head = InitHead; }
int GetHead() { return Head; }
void EnterQuads(int InitNumQuads);
int ActionForQuad(int InitStart, char InitReadin);
void ShowQuads(int InX, int InY);
void ApplyQuads();
};
The Splash Screen Data File.
Hello. This is a small program, written in C++, that acts as a very limited Turing Machine tester. Restricted to an alphabet of a single character (I) and inputs of one or two strings only, it still allows a large range of machines to be built and applied to input. Due to an 18 credit load and a complete lack of ample time, the code has NO error traps or nicities. What occurs if a machine is entered incorrectly or is just wrong is anyone's guess. Also, when entering a machine DO NOT add the Q in front of states. Just enter a number, then the Read Symbol, then the Action, then just a number for the final state. For example, enter a f(x) = x+1 machine as : 1 B R 2 <enter> 2 I R 2 <enter> 2 B I 3 <enter> 3 I L 3 <enter> That's about all. You'll catch on to the rest. Future features will include proper error traps, unlimited tape (Now only 40), and a "step-through" feature to watch the effect of each individual quad as the machine runs on the input. Hope you like. Lars Sorensen
The Driver
// Shell for Turing Machine Program
// AUTHOR : Lars Sorensen
#include <iostream.h>
#include <conio.h>
#include <fstream.h>
#include <stdlib.h>
#include <graphics.h>
#include "Turing.h"
void main(void)
{
int Choice;
TuringMachine M(60);
gotoxy(1,1);
textcolor(WHITE);
textbackground(BLUE);
clrscr();
while (1)
{ //while
clrscr();
cout << " The Turing Machine Processing Program\n\n";
cout << " 1. Instructions and Excuses.\n";
cout << " 2. Create (or change) an Input Tape.\n";
cout << " 3. Build a Turing Machine (Enter Quadruples) \n";
cout << " 4. Inspect your Tape.\n";
cout << " 5. Inspect your Turing Machine Quadruples.\n";
cout << " 6. Apply the Machine's Quads to the Input Tape.\n";
cout << " 7. Exit the Program.\n\n";
cout << " Enter The Choice : ";
cin >> (Choice);
switch (Choice) {
case 1 :
{
char ch;
ifstream infile("a:turing.doc");
clrscr();
cout << '\n';
while(infile)
{
infile.get(ch);
cout << ch;
}
cout << "\n Press a Key to Return to Menu";
getch();
break;
}
case 2 :
{
int NumPuts, In1, In2=0;
clrscr();
gotoxy(1,3);
cout << " OK.. Now it's time to enter the Input tape that your \n"
<< " machine will work on. As you've been told, this program\n"
<< " works on very, very, limited versions of the machines.\n"
<< " You're input is limited to an alphabet of one symbol, I.\n"
<< " Because the tape has been initialized with B's all this\n"
<< " program needs is the number of I's to place on the tape.\n"
<< " The program also allows tapes with two input strings.\n\n"
<< " Now, Enter how many Inputs you'll need (1 or 2): ";
cin >> NumPuts;
if( NumPuts != 1 )
{
cout << "\n Enter the Number of I's you need for Input 1 : ";
cin >> In1;
cout <<"\n Enter the Number of I's you need for Input 2 : ";
cin >> In2;
}
else
{
cout <<"\n Enter the Number of I's you need : ";
cin >> In1;
}
M.SetInput(In1,In2);
cout << "\n\nThanks.... Press a Key to Inspect the Tape.";
clrscr();
M.ShowTape(10,12);
getch();
break;
}
case 3 :
{
int NumQ;
clrscr();
gotoxy(1,3);
cout << " \n";
cout << " \n";
cout << " \n";
cout << " \n";
cout << " \n";
cout << " \n";
cout << " \n";
cout << " \n\n";
cout << " Enter the Number of Quadruples for your Machine : ";
cin >> NumQ;
clrscr();
gotoxy(2,2);
cout << "Now Enter Your Turing Machine\n\n";
M.EnterQuads(NumQ);
break;
}
case 4 :
{
clrscr();
M.ShowTape(10,12);
getch();
break;
}
case 5 :
{
clrscr();
M.ShowQuads(20,3);
break;
}
case 6 :
{
clrscr();
gotoxy(2,2);
cout << "Here is your Input Tape.";
M.ShowTape(2,4);
gotoxy(2,7);
cout << "Press a Key and Your Machine will be run on the Tape.\n";
getch();
M.ApplyQuads();
gotoxy(2,11);
cout << "Here is the Output Tape.";
M.ShowTape(2,13);
gotoxy(2,16);
cout << "Press a Key to return to the Menu.";
getch();
break;
}
case 7 :
{
textcolor(WHITE);
textbackground(BLACK);
clrscr();
exit(0);
}
} //switch
} //while
// That's All Folks.....
}
The Guts
#include <iostream.h>
#include <conio.h>
#include <stdlib.h>
#include "Turing.h"
TuringMachine::TuringMachine(int InitTapeMax)
{
Tape = new char[InitTapeMax-1];
for (int i=0; i < TapeMax; i++ ) Tape[i] = 'B';
TapeMax = InitTapeMax;
StartingPoint = (TapeMax/2)-1;
Head = StartingPoint;
InitTape();
}
void TuringMachine::SetInput(int Input1,int Input2)
{
Head = StartingPoint;
InitTape();
if ( Input2 == 0 )
{
MoveRight();
for (int j=(StartingPoint+1); j < (Input1+StartingPoint+1); j++)
{
WriteSymbol('I');
MoveRight();
}
}
else
{
MoveRight();
for (int j=(StartingPoint+1); j < (Input1+StartingPoint+1); j++)
{
WriteSymbol('I');
MoveRight();
}
MoveRight();
for (int k=(StartingPoint+Input1+2); k < (Input2+StartingPoint+Input1+2); k++)
{
WriteSymbol('I');
MoveRight();
}
}
Head = StartingPoint;
}
void TuringMachine::ShowTape(int InX, int InY)
{
// The Actual Tape
gotoxy(InX,InY);
for (int i=0; i < TapeMax; i++) cout << Tape[i];
// The Head Position
gotoxy(InX,InY+1);
HeadString = new char[TapeMax-1];
for (int k=0; k < TapeMax; k++) HeadString[k]=' ';
HeadString[Head] = '^';
for (int j=0; j < TapeMax; j++) cout << HeadString[j];
}
void TuringMachine::InitTape()
{
for (int i=0; i < TapeMax; i++) Tape[i]='B';
}
void TuringMachine::InitHead()
{
Head = (TapeMax/2)-1;
}
void TuringMachine::MoveRight()
{
if ( Head == (TapeMax-1) )
{
cout << "Cannot Move Tape Any Further to the Right";
}
else
{
Head++; // I know you don't need the brackets...Readability people!!
}
}
void TuringMachine::MoveLeft()
{
if ( Head == 0 )
{
cout << "Cannot Move Tape Any Further to the Left";
}
else
{
Head--;
}
}
void TuringMachine::WriteSymbol(char Sym)
{
Tape[Head] = Sym;
}
void TuringMachine::EnterQuads(int InitNumQuads)
{
NumQuads = InitNumQuads;
Starts = new int[NumQuads];
Readins = new char[NumQuads];
Actions = new char[NumQuads];
Finis = new int[NumQuads];
cout << "\nPlease Enter, in order, the Start State, "
<< "the Reading Symbol ( B or I ),\n"
<< "the Action to take ( R,L,I ), and "
<< "the Finish State ... \n";
for ( int i=0; i < NumQuads; i++)
{
cin >> Starts[i] >> Readins[i] >> Actions[i] >> Finis[i];
}
cout << "Thank You...Press a Key to Continue.\n";
getch(); // old C cheatin...where's stdio.h when you need it?
}
void TuringMachine::ShowQuads(int InX, int InY)
{
for ( int j=0; j < NumQuads; j++)
{
gotoxy(InX,InY+j);
cout << 'Q' << Starts[j] << ' '
<< Readins[j] << ' '
<< Actions[j] << ' '
<< 'Q' << Finis[j];
}
getch();
}
int TuringMachine::ActionForQuad(int InitStart, char InitReadin)
{
for(int i=0; i < NumQuads; i++ )
{
if ((InitStart==Starts[i]) && (InitReadin==Readins[i])) return i;
}
return -1;
}
void TuringMachine::ApplyQuads()
{
int CurrentState=1,NextState;
char CurrentSymbol,NextAction;
int NextIndex;
while(1)
{
CurrentSymbol = Tape[Head];
NextIndex = ActionForQuad(CurrentState,CurrentSymbol);
if ( NextIndex == -1 ) break;
NextAction = Actions[NextIndex];
NextState = Finis[NextIndex];
if ( NextAction == 'B' ) WriteSymbol('B');
if ( NextAction == 'I' ) WriteSymbol('I');
if ( NextAction == 'R' ) MoveRight();
if ( NextAction == 'L' ) MoveLeft();
CurrentState = NextState;
}
cout << "\n Machine has halted reading a " << CurrentSymbol
<< " in state " << CurrentState << '\n';
} // end of source