C or C++ code help (NFA RECOGNIZER)

[coolguythampy]

Hello,

I need help with a C or TURBO CPP program that can recognize a non deterministic finite state automata and display message if it is accepted or not. Can you point me to such a program code? I cant find it anywhere on the net

[it career]

You mean something like whether a language belongs to NP or not ?

[coolguythampy]

Yes. It should take a string as input and say if it is accepted by the nfa or not

[Gox]

If it doesn't have to be C, then JFLAP might be a useful tool.

[coolguythampy]

We can do only in PERL or CPP. But since none of my friends or myself know PERl we have no other option rather than go with CPP. That too turbo CPP. It's the only tool we are trained with. i got a code which uses header files like #include <vector> etc. Is it ANSI C????

[coolguythampy]

Here is the code I wrote

#include<iostream.h>
#include<conio.h>
#include<ctype.h>
#include<stdio.h>
#include<string.h>
#include<process.h>
struct DFASTATES
{
 int initial;
 char input_symbol;
 int final;
}dfa[50];
int  di=0;
int stack[100],top=0,stack1[100],top1=0,stack3[100],top3=0,stack4[100],top4=0;
void main()
{
  clrscr();
  char str[50],ch;
  int m,starti,endi,i,n,j;
  cout<<"Enter the no: of states"<<endl;
  cin>>n;
  cout<<"Enter the states  <initial> <i/p> <final>"<<endl;
  for(i=0;i<n;i++)
  {
   cin>>dfa[di].initial>>dfa[di].input_symbol>>dfa[di].final;
   di++;
  }
  for(i=0;i<n-1;i++)
  {
  if((dfa[i].initial==dfa[i+1].initial)&&(dfa[i].input_symbol==dfa[i+1].input_symbol))
    {
     stack[top]=i+1;
     i++;
     top++;
    }
  }
  m:
  cout<<"\nEnter the initial and final states : ";
   cin>>starti>>endi;
  cout<<"\nEnter the i/p string : ";
   gets(str);
  int  flag=0;
  for(i=0;str[i]!='\0';i++)
  {
   flag=0;
   ch=str[i];
   for(j=0;j<n;j++)
   {
   if(dfa[j].initial==starti)
   {
    if(dfa[j].input_symbol==ch)
   {
      starti=dfa[j].final;
      flag=1;
      for(int z=0;z<top;z++)
      {
       if(j+1==stack[z])
       {
	 stack1[top1]=i;
	 top1++;
	 stack4[top4]=j;
	 top4++;
       }
      }
     break;
    }
    }
    }
     if(flag==0)
     {
       stack3[top3]=i-1;
       cout<<i;
       top3++;
      break;
     }  }
   if((starti==endi)&&(flag!=0))
   {
    cout<<" the string is accepted "<<endl;
   }
   else
    {
      top3=top3-1;
      top--;
      top4--;
      if((str[stack3[top3]]==dfa[stack[top]].input_symbol)&&(dfa[stack4[top4]].initial==dfa[stack[top]].initial))
      {
	starti=dfa[stack[top]].final;
	for(i=stack3[top3]+1;str[i]!='\n';i++)
	{
	 flag=0;
	 ch=str[i];
	 for(j=0;j<n;j++)
	 {
	  if(dfa[j].initial==starti)
	  {
	   if(dfa[j].input_symbol==ch)
	   {
	      starti=dfa[j].final;
	      flag=1;
	      for(int z=0;z<top;z++)
	      {
	       if(j+1==stack[z])
	       {
		stack1[top1]=i;
		top1++;
	       }
	      }
	      break;
	    }
	   }
	  }
     if(flag==0)
     {
      getch();
      break;
     }
     }
     }
     }
     if((starti==endi)&&(str[i]=='\0'))
      cout<<" the string is accepted "<<endl;
     else
      cout<<" the string is not accepted "<<endl;
     for(i=0;i<top;i++)
      cout<<stack[i]<<endl<<stack1[i];
     getch();
     cout<<"Do you want to continue? (y/n) : ";
     cin>>ch;
     if(ch=='y'||ch=='Y')
      goto m;
     else
      exit(0);

}

Any suggestions?