C program to implement DFA

//updated on 11/03/2015

Hello friends,

               This post describes how a Deterministic Finte Automata (DFA) can be implemented using C. Do you know, associated with every programming language compiler there is a program named  recognizer that takes a string , say string S, as input and answers "YES" if S is a sentence of the language and  " NO " otherwise..!! To accomplish this , we have to train recognizer about the syntactic structure of intended language ( done with regular expressions). For this purpose, we construct a transition diagram called a "finite automation". In a Deterministic Finite Automation, only one transition out of state is possible on the same input symbol. On the other hand, in NonDeterministic Finite Automata more than one transitions may possible for same input symbol.

  . Some interesting implementations using DFA are:

• whether DFA accepts all strings.
• whether DFA accepts any string
• whether two DFAs recognize the same language
• DFA with a minimum number of states for a particular regular language

Illustartion


Consider the DFA represented in this transition diagram.



   

                         


Here is a sample DFA with starting state " 0 ", and accepting state " 1" .  "a" and "b" are the input symbols.
This DFA will accept any string containing 'a's and 'b' and last symbol should be 'a'.


CODE:


#include <stdio.h>

#define TOTAL_STATES 2

#define FINAL_STATES 1

#define ALPHABET_CHARCTERS 2

#define UNKNOWN_SYMBOL_ERR 0

#define NOT_REACHED_FINAL_STATE 1

#define REACHED_FINAL_STATE 2

enum DFA_STATES{q0,q1};

enum input{a,b};

int Accepted_states[FINAL_STATES]={q1};

char alphabet[ALPHABET_CHARCTERS]={'a','b'};

int Transition_Table[TOTAL_STATES][ALPHABET_CHARCTERS];

int Current_state=q0;

void DefineDFA()

{

    Transition_Table[q0][a] = q1;

    Transition_Table[q0][b] = q0;

    Transition_Table[q1][a] = q1;

    Transition_Table[q1][b] = q0;

}

int DFA(char current_symbol)

{

int i,pos;

    for(pos=0;pos<ALPHABET_CHARCTERS; pos++)

        if(current_symbol==alphabet[pos])   

            break;//stops if any character other than a or b

    if(pos==ALPHABET_CHARCTERS)

         return UNKNOWN_SYMBOL_ERR;

    for(i=0;i<FINAL_STATES;i++)

 if((Current_state=Transition_Table[Current_state][pos])

==Accepted_states[i])

            return REACHED_FINAL_STATE;

    return NOT_REACHED_FINAL_STATE;

}

int main(void)

{

    char current_symbol;

    int result;

    DefineDFA();    //Fill transition table

    printf("Enter a string with 'a' s and 'b's:\n

                Press Enter Key to stop\n");

    while((current_symbol=getchar())!= '\n')

        if((result= DFA(current_symbol))==UNKNOWN_SYMBOL_ERR)

            break;

    switch (result) {

    case UNKNOWN_SYMBOL_ERR:printf("Unknown Symbol %c",

  current_symbol); 

 break;

    case NOT_REACHED_FINAL_STATE:printf("Not accepted"); break;

    case REACHED_FINAL_STATE:printf("Accepted");break;

    default: printf("Unknown Error");

    }

    printf("\n\n\n");

    return 0;

}

OUTPUT
========

String with only "a"s and "b"s and last symbol is "a".     ACCEPTED..!!

String with only "a"s and "b"s but  last symbol is not  "a".     REJECTED..!!

Unknown symbol "y" in input. REJECTED.!!!!

Read more »

C PROGRAM TO DISPLAY TYPE OF A FILE

Hi Friends,

This is my C program to check the type of a file in UNIX system. Before going to program, have a look on what actually a 'type' means in UNIX system. A file may be one of the  following types :

1. Regular File  : It may be either a text file or a binary file.
2. Directory File : These are the files that can store other files (like file folder we use) so that users can organise their files into some hierarchical manner.!!)
3. Character Device File : It refers to a physical device that transmits data in a character-based manner. (like printer, modems, consoles),
4. Block Device File : Similar to character device file, but it can transmit a block  of data at a time.
5. FIFO FILE : A special pipe device file which furnishes a temporary buffer for 2 or more processes to communicate (by writing to / reading data from buffer).

Note: A single device can have both block and character device files representing them for different access methods.Consider F be a character device file on its creation. But F can be used by a hard disk to bulk/ non-blocking data transfer between a process and the disk.

         Here is the complete program. . .

TYPECHECK.C 

 /*
PROGRAM NAME: TYPECHECK.C
AIM : TO READ A FILE NAME AND DISPLAY IT'S TYPE
DATE : 07/31/2011
*/

  #include<stdio.h>                                                                           
  #include<sys/stat.h>                                          
                                                                             
  main ()
 {   
    char file_name[20];
    struct stat p;
    printf("\nEnter filename :  ");
    scanf("%s",file_name);
    stat(file_name,&p);
    printf("\a\n%s is a ",file_name); 
    if(S_ISREG(p.st_mode))
    printf("regular file");
     else if(S_ISDIR(p.st_mode))
     printf("directory file");

     else if(S_ISCHR(p.st_mode))
     printf("character file");
     else if(S_ISBLK(p.st_mode))
     printf("block file");
      else if(S_ISFIFO(p.st_mode))
      printf("FIFO file");
      else
      printf("Unknown type file or not found..!!");
      getch();
     

 }                   



Read more »

C PROGRAM TO IMPLEMENT MACRO PROCESSOR

 Here is my C program implementing a Macro Processor. We know that Macro is a single line abbreviation for a group of statements. We should define that sentence - cluster before using them in actual program. Macro processor will analyse the program and on encountering  macro variable, it will replace that 'Macro invocation' to corresponding Macro definition. It should also take care the number  and position of arguments used in Macro invocation.

ALGORITHM

MACROPROCESSOR

• EXPANDING=FALSE.
• Read each line and call GETLINE() and PROCESSLINE() until END encounters.

PROCESSLINE ( )

• If OPCODE is a macroname then EXPAND ( ).
• Else if OPCODE is MACRO ,then DEFINE ( ).
• Else write line to expanded file as such.

DEFINE( )

• Enter Macro name into NMATAB.
• Enter macro prototype into DEFTAB.
• Set LEVEL=1.
• Substitute parameters with positional notations and enter to DEFTAB.
• If OPCODE=MACRO, LEVEL++;
• If OPCODE=MEND, LEVEL--;
• Continue this until LEVEL=0
• Store beginning and end of definition as pointers within NAMTAB

EXPAND ( )

• EXPANDING = TRUE
• Set up arguments from macro invocation in ARGTAB.
• Write macro invocation statement to expanded file  as a comment line.
• Call GETLINE() and PROCESSLINE() till macro definition ends.
• Set EXPANDING=FALSE.

GETLINE ( )

• If EXPANDING is TRUE, read from DEFTAB (data structure where macro body is stored) and substitute arguments for positional notations.
• If  EXPANDING is FALSE , read next line from input file.

MACROPROCESSOR.C

 /*

PROGRAM NAME:MACRO.C

AIM: TO IMPLEMENT MACRO PROCESSOR.

INPUT : "INPUT.TXT"

OUTPUT: "EXPANDED.TXT"

DATE: 07/28/2011

*/

#include<stdio.h>

#include<string.h>

void GETLINE();

void PROCESSLINE();

void DEFINE();

void EXPAND();

 FILE *expanded;

 FILE *input;

 char label[10],opcode[10],operand[25];

 char line[20];

 int namcount=0, defcount=0;

 int EXPANDING;

 int curr;

 struct namtab

 {

 char name[10];

 int start,end;

}mynamtab[15];

     

 struct deftab

 {

        char macroline[25];

  }mydeftab[25];

struct argtab

{

       char arg[3][9];

 }myargtab;

///MACRO MAIN

int main()

{

    EXPANDING=0;

    input =fopen("input.txt","r");                          

 expanded=fopen("expanded.txt","w");

GETLINE();

 

     while(strcmp(opcode,"END")!=0)

{  

     PROCESSLINE();

       GETLINE();

 }

              fprintf(expanded,"%s",line);

      getch();

     return 1;

  }

                            

//   GETLINE

     void GETLINE()

     {    char word1[10],word2[10],word3[10],buff[10];

int count=0,i,j=0;

if(EXPANDING)strcpy(line,mydeftab[curr++].macroline);

 else fgets(line,20,input);

        opcode[0]='\0';label[0]='\0';operand[0]='\0';word1[0]='\0';word2[0]='\0';word3[0]='\0';

        

                      for(i=0;line[i]!='\0';i++)

                      {

                                        

                                                if(line[i]!=' ')

                                                buff[j++]=line[i];

                    

                                                 else

                      {

                                                   

                      buff[j]='\0';

                 

                   

                      strcpy(word3,word2);

                      strcpy(word2,word1);

                       strcpy(word1,buff);

                     j=0;count++;

                      }

                    

                    

                      }

                       buff[j-1]='\0';

                      strcpy(word3,word2);

                      strcpy(word2,word1);

                       strcpy(word1,buff);

                   

   

      switch(count)

                       {

                                    case 0:strcpy(opcode,word1);break;

                                    case 1:{strcpy(opcode,word2);strcpy(operand,word1);}break;

                                    case 2:{strcpy(label,word3);strcpy(opcode,word2);strcpy(operand,word1);}break;

                       }

                   

                     

                       }

                   

//     PROCESSLINE

                       void PROCESSLINE()

                       {

                            int i;

                        for(    i=0;i<namcount;i++)

                      

                                if(!strcmp(opcode,mynamtab[i].name))

                                {

                                                               

                                                                  EXPAND();return;

                                                          

                                                        

                                                             

                                                                  }

                                                           

                                                               { 

                                                                  if(!strcmp(opcode,"MACRO"))

                                                                

                                                                 DEFINE();

                                                               

                                                                 else fprintf(expanded,"%s",line);

                                                                   }

                                                                   }

   

   

     void DEFINE()

     {

          int LEVEL,i=0,j=0,k=0;

       char param[5][9];

       char s[3];

      strcpy(s,"123");

 

          strcpy(mynamtab[namcount].name,label);

          mynamtab[namcount].start=defcount;

          strcpy(mydeftab[defcount].macroline,line);

      

       

          while(operand[i]!='\0')

          {

                                if(operand[i]!=',')

                                param[j][k++]=operand[i];

                                else

                                {

                                    param[j++][k]='\0';

                                

                                    k=0;

                                    }

                              

                               i++;

                                }

                                param[j][k]='\0';

                             

        

          LEVEL=1;

     

        while(LEVEL>0)

          {

                   

            GETLINE();

           

              if(operand[0]!='\0')

             {

            for(i=0;i<3;i++)

            {

            if(!strcmp(operand,param[i]))

            {

            operand[0]='?';

            operand[1]=s[i];

            operand[2]='\0';

             }

             }

             }

           if(!strcmp(opcode,"MACRO"))

            LEVEL++;

           else if(!strcmp(opcode,"MEND"))

            LEVEL--;

            strcpy(mydeftab[defcount].macroline,opcode);

            if(operand[0]!='\0')

            {

            strcat(mydeftab[defcount].macroline," ");

            strcat(mydeftab[defcount].macroline,operand);

            strcat(mydeftab[defcount].macroline,"\n");

            }

            strcat(mydeftab[defcount++].macroline,"\n");

                        }

                        mynamtab[namcount++].end=defcount;

                   

                    

                        }

                      

         

//Expand
        

    void EXPAND()

                        {

                             int i,end=0,j=0,k=0;

                             EXPANDING=1;

                             int arg=0;

                      

                         fprintf(expanded,"//%s",line);

                             for(i=0;i<namcount;i++)

                             {

                             if(!strcmp(opcode,mynamtab[i].name))

                             {

                                                             

                             curr=mynamtab[i].start;

                             end=mynamtab[i].end;

                          

                           

                                   while(operand[i]!='\0')

                                {

                                if(operand[i]!=',')

                                myargtab.arg[j][k++]=operand[i];

                                else

                                {

                                    myargtab.arg[j++][k]='\n';

                                

                                    k=0;

                                    }

                              

                               i++;

                                }                              

                                 myargtab.arg[j][k]='\n';

                           

                        

                             }

                             }

                           

                             while(curr<(end-1))

                             {

                                              GETLINE();

                           if(operand[0]=='?')

                                         

                          strcpy(operand,myargtab.arg[operand[1]-'0'-1]);

                           fprintf(expanded,"%s %s %s",label,opcode,operand);

                        

                             }

                             EXPANDING=0;

                           

                           

                         }



/*************************************************************************************/


  Let us have a look on what will be the output of the program for a sample input.


input.txt



COPY START 1000

RDBUFF MACRO P,Q,R
CLEAR A
CLEAR S
CLEAR X
+LDT #4096
TD P
JEQ *-3
RD P
STCH Q
JLT *-19
LDA R
COMP #0
STX R
MEND

//main program





FIRST STL RETADR
RDBUFF F1,BUFF1,L1
CLEAR X
RDBUFF F2,BUFF2,L2
RDBUFF F3,BUFF3,L3
JLT *-19
STA
END



The output produced will be,

expanded.txt

COPY START 1000
//main program
FIRST STL RETADR
//RDBUFF F1,BUFF1,L1
 CLEAR A
 CLEAR S
 CLEAR X
 +LDT #4096
 TD F1
 JEQ *-3
 RD F1
 STCH BUFF1
 JLT *-19
 LDA L1
 COMP #0
 STX L1
CLEAR X
//RDBUFF F2,BUFF2,L2
 CLEAR A
 CLEAR S
 CLEAR X
 +LDT #4096
 TD F2
 JEQ *-3
 RD F2
 STCH BUFF2
 JLT *-19
 LDA L2
 COMP #0
 STX L2
//RDBUFF F3,BUFF3,L3
 CLEAR A
 CLEAR S
 CLEAR X
 +LDT #4096
 TD F3
 JEQ *-3
 RD F3
 STCH BUFF3
 JLT *-19
 LDA L3
 COMP #0
 STX L3
JLT *-19
STA
END

        

Read more »

To Read Student Details and Make Rank List

Here is a simple C program that can be used to input students details. The program can store the details into a file and from that file it can make a rank list which can be written to another file.!! On reading the aim it is obvious that actual file handling may not be in same manner. But this program surely introduce you how Actual file 'read ' and 'write' occurs. Here we go..

STUDENT.C

/*

*PROGRAM NAME:STUDENT.C

*AIM : TO READ STUDENT DETAILS AND MAKE PROGRESS REPORT IN A FILE

*OUTPUT FILE: STUDENT.TXT , PROGRESS. TXT

*DATE: 07/30/2011

*/

#include<stdio.h>
#include<fcntl.h>
struct student
{
       int roll_no,total;
       char Name[10];
        }
       buff,stud[20];
      
       int main()
       {

           int count,i,j;
           int fd=open("STUDENT.TXT",O_WRONLY|O_APPEND);  //open 'student.txt' to write unsorted student-details
           printf("Enter the no. of students..");
           scanf("%d",&count);
           for( i=0;i<count;printf("\n"))
           {
           printf("Student %d\n",++i);
           printf("Roll no : ");
           scanf("%d",&buff.roll_no);
           printf("Name : ");
           scanf("%s",buff.Name);
           printf("Total Marks : ");
           scanf("%d",&buff.total);
           write(fd,&buff,sizeof(buff));  //Store each data in a "buffer" structure and append to 'student.txt'..
           }                                            
            close(fd);
            
             fd=open("STUDENT.TXT",O_RDONLY);
            int fd2=open("PROGRESS.TXT",O_WRONLY);
            count=0;
            while(read(fd,&buff,sizeof(buff))>0)  //Open 'student.txt' in read mode and copy data to structure-array..
                 stud[count++]=buff;
                
               for(i=0;i<count;i++)                //Sort the details in structure array
               for(j=0;j< count-i-1;j++)
               if(stud[j].total<stud[j+1].total)
               {
                buff=stud[j];
                stud[j]=stud[j+1];
                stud[j+1]=buff;
                }
               for(i=0;i<count;i++)
               write(fd2,&stud[i],sizeof(stud[i]));//Write back the sorted details to 'progress.txt'..
               close(fd2);
               close(fd);
               fd2=open("PROGRESS.TXT",O_RDONLY); //Open 'progress.txt' file to read and display ranklist 
               printf("\n\tPROGRESS REPORT\n\t_______________\n\n\n RANK\t NAME \tROLLNO\tMARKS\n\n");
               i=0;
               while(read(fd2,&buff,sizeof(buff))>0)
               printf("\n (%d)\t%s\t%d\t%d",++i,buff.Name,buff.roll_no,buff.total);
               getch();
                           }

Read more »