Hello and welcome to our community! Is this your first visit?
Register
Enjoy an ad free experience by logging in. Not a member yet? Register.
Results 1 to 6 of 6
  1. #1
    New Coder
    Join Date
    Mar 2009
    Posts
    25
    Thanks
    0
    Thanked 0 Times in 0 Posts

    C or C++ code help (NFA RECOGNIZER)

    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

  • #2
    Banned
    Join Date
    Jun 2007
    Location
    Web Designer
    Posts
    321
    Thanks
    0
    Thanked 6 Times in 6 Posts
    You mean something like whether a language belongs to NP or not ?

  • #3
    New Coder
    Join Date
    Mar 2009
    Posts
    25
    Thanks
    0
    Thanked 0 Times in 0 Posts
    Yes. It should take a string as input and say if it is accepted by the nfa or not

  • #4
    Gox
    Gox is offline
    Regular Coder Gox's Avatar
    Join Date
    May 2006
    Location
    Ontario, Canada
    Posts
    392
    Thanks
    2
    Thanked 20 Times in 20 Posts
    If it doesn't have to be C, then JFLAP might be a useful tool.

  • #5
    New Coder
    Join Date
    Mar 2009
    Posts
    25
    Thanks
    0
    Thanked 0 Times in 0 Posts
    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????

  • #6
    New Coder
    Join Date
    Mar 2009
    Posts
    25
    Thanks
    0
    Thanked 0 Times in 0 Posts
    Here is the code I wrote

    Code:
    #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?


  •  

    Tags for this Thread

    Posting Permissions

    • You may not post new threads
    • You may not post replies
    • You may not post attachments
    • You may not edit your posts
    •