07-05-2011, 12:52 PM
Objective
Program in “C” to implement NFA.
Code:
#include<stdio.h>
#include<conio.h>
int check(char* s,int state);
int a[10][10][10], fs[10],n;
int main()
{
int initial,i,j,k,l;
char ch,str[25];
clrscr();
printf("Enter no.of states \n");
scanf("%d",&n);
printf("enter initial state \n");
scanf("%d",&initial);
printf("Enter final states \n");
for(i=0;i<n;i++)
{
printf("\nq");
scanf("%d",&fs[i]);
if(fs[i]<0)
break;
}
for(i=0;i<=n;i++)
for(j=0;j<2;j++)
for(k=0;k<n;k++)
{
printf("(q%d,%d)=q",i,j);
scanf("%d",&a[i][j][k]);
if(a[i][j][k]<0)
break;
}do {printf("enter the string\n");
scanf("%s",str);
//r(l=0;l<strlen(str);l++)
if(check(str,initial))
printf("string is accepted");
else
printf("not accepted");
printf("\n\n input another (y/n)");
scanf("%s",&ch);
}
while(ch!='n');
return 0; //tch();
}
int check(char* s,int state)
{
int i,j;
for(i=0;i<n;i++)
{
if(*s=='\0')
{
if(fs[i]<0)
break;
if(fs[i]==state)
return 1;
}else{j=a[state][(int)(*s-'0')][i];
if(j<0)
break;
if(check(s+1,j))
return 1;
}}
return 0;
}