...

View Full Version : C or C++ code help (NFA RECOGNIZER)



coolguythampy
07-30-2009, 06:38 PM
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
07-31-2009, 10:27 AM
You mean something like whether a language belongs to NP or not ?

coolguythampy
07-31-2009, 01:25 PM
Yes. It should take a string as input and say if it is accepted by the nfa or not

Gox
08-01-2009, 12:11 AM
If it doesn't have to be C, then JFLAP might be a useful tool.

coolguythampy
08-01-2009, 06:10 AM
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
08-03-2009, 06:46 PM
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?



EZ Archive Ads Plugin for vBulletin Copyright 2006 Computer Help Forum