abab.cpp

An automata implemented in C++ for searching a string of "abab" in a given string.

#include <iostream.h>
#include <conio.h>
#include <string.h>


const int size = 30;

int state[11][3]={
						{2,7,7},{7,3,2},{7,3,4},{7,5,2},{7,3,6},{8,9,6},
						{7,7,7},{8,8,8},{8,9,10},{8,11,6},{8,10,9}
					  };

void check_abab(char array[])
{
	int nextState;
	int input=0,statePtr=1,curState;

	while(1)
	{
		if(array[input]=='B')
		{
			nextState = state[statePtr-1][0];
			statePtr = nextState;

			if(statePtr == 7 || statePtr == 8)
				break;

			input++;
		}

		if(array[input]=='a')
		{
			nextState = state[statePtr-1][1];
			statePtr = nextState;
			input++;
		}

		if(array[input]=='b')
		{
			nextState = state[statePtr-1][2];

			if(statePtr==5 || statePtr==11)
				array[input]='c';

			statePtr = nextState;
			input++;
		}
	}
	if(statePtr == 8)
		cout <<"String contains 'abab' substring."<<endl<<array;
	else
		cout <<"String does not contain 'abab' substring.";

}

void takeInput(char array[])
{
	cout <<"Please enter the String..."<<endl;
	cin >> array;
	for(int i=0;i<strlen(array);i++)
	{
		if(array[i]!='a' && array[i]!= 'b' && array[i]!='B')
		{
			cout <<"This machine only accept alphabets 'a' or 'b'";
			break;
		}
	}
}

void main()
{
	clrscr();
	char array[size];
	takeInput(array);
	check_abab(array);
	getch();
}