Search Tutorials

Loading...

Friday, 24 May 2013

C code to implement NFA(Non-Deterministic Finite Automata)

/* C program to implement NFA(Non-Deterministic Finite Automata). */


#include<stdio.h>
#include<conio.h>
int Fa[10][10][10],states[2][10],curr,row=0,col=0,sr=0,sc=0,th=0,in;
char *str;
int nfa(char *string,int state)
 {
    int i,j;
    for(i=0;i<=row;i++)
         {
           if(*string)
               {
            curr=Fa[state][*string-97][i];

              if (curr==-1)
                break;
              if(nfa(string+1,curr))
                return 1;
               }
            else
               {
               if(states[1][i]==-1)
              break;
               if(state==states[1][i])
              return 1;
               }
           }
           return 0;
      }
int main()
  {
     FILE *fp;
     int i,j,k,flag=0;
     char c,ch;
     clrscr();
     fp=fopen("Nfa_ip.txt","r");

     for(i=0;i<2;i++)
       for(j=0;j<10;j++)
     states[i][j]=-1;

     for(i=0;i<10;i++)
       for(j=0;j<10;j++)
      for(k=0;k<10;k++)
          Fa[i][j][k]=-1;

     while(fscanf(fp,"%d",&in)!=EOF)
       {
       fscanf(fp,"%c",&c);

        if(flag)
          {
         states[sr][sc++]=in;
         if(c=='\n')
            {
              sr++;
              sc=0;
            }
          }
        else if(c=='#')
          {
         flag=1;
         Fa[row][col][th]=in;
         printf("\nFa[%d][%d][%d]=%d",row,col,th,Fa[row][col][th]);

          }
         else if(!flag)
          {
         Fa[row][col][th]=in;
         printf("\nFa[%d][%d][%d]=%d",row,col,th,Fa[row][col][th]);
         if(c==',')
           {
             th++;
           }
         else if(c=='\n')
           {
              col=0;
              row++;
              th=0;
          }
        else if(c!=',')
         {
             col++;
             th=0;
          }
          }

      }

      printf("\n\nEnter the string : \n");
      scanf("%s",str);

      if(nfa(str,states[0][0]))
    printf("\nString Is Accepted");
       else
    printf("\nString Not Accepted");
     getch();

     return 0;
  }


Input File For NFA Program:

1,2 1
-1 2
-1 -1#
0
2


For more C programs related to Automata, Check Automata label. Share and comment to improve this blog.

Related Programs:-

★ Convert NFA to DFA

★ Lexical Analyzer

★ Syntax Tree

★ Calculate In and Out

9 comments:

  1. Thanks you!!! admins.
    It's very usefull for us

    ReplyDelete
    Replies
    1. Welcome bro..share and help others.

      Delete
  2. admin this is invisible for me !! why don't you use some comments to make this code more visible

    ReplyDelete
    Replies
    1. Thanks for suggestion..we will do soon.

      Delete
  3. hello admin you have forgotten the definition of clrscr(); function
    cuz i don't find it in the code

    ReplyDelete
  4. For what NFA this implementation is for ?

    ReplyDelete
  5. Replies
    1. Input file is given above.

      Delete

Back to Top