C program for DFA

By -

DFA which accept the string (ab)*b (String ending with b).


#include <stdio.h>
#define TOTAL_STATES 4
#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,q2,q3};
enum input{a,b};
int Accepted_states[FINAL_STATES]={q2};
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] = q2;
    Transition_Table[q1][a] = q3;
    Transition_Table[q1][b] = q0;
    Transition_Table[q2][a] = q3;
    Transition_Table[q2][b] = q3;
    Transition_Table[q3][a] = q3;
    Transition_Table[q3][b] = q3;
}
int DFA(char current_symbol)
{
int i,pos;
    for(pos=0;pos<ALPHABET_CHARCTERS; pos++)
        if(current_symbol==alphabet[pos])
            break;//stops if symbol is defferent
    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();
    printf("Enter a string with 'a' s and 'b's:\n\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;
}



Comments

Post a Comment

Popular posts from this blog

C program that contains a string XOR each character in this string with 0 ,127

By -
Write a C program that contains a string (char pointer) with a value \Hello World’. The program should XOR each character in this string with 0 and displays the result. Program: #include<stdlib.h> main() { char str[]="Hello World"; char str1[11]; int i,len; len=strlen(str); for(i=0;i<len;i++) { str1[i]=str[i]^0; printf("%c",str1[i]); } printf("\n"); } Q.2 Write a C program that contains a string (char pointer) with a value \Hello World’. The program should AND or and XOR each character in this string with 127 and display the result. PROGRAM: #include <stdio.h> #include<stdlib.h> void main() { char str[]="Hello World"; char str1[11]; char str2[11]=str[]; int i,len; len = strlen(str); for(i=0;i<len;i++) { str1[i] = str[i]&127; printf("%c",str1[i]); } printf("\n"); for(i=0;i<len;i++) { str3[i] = str2[i]^127; printf("%c",str3[i]); } pri
Read more

Queue in Data Structure(DS)

By -
Image
Queue Queues are data structures that follow the First In First Out (FIFO) i.e. the first element that is added to the queue is the first one to be removed. Elements are always added to the back(rear) and removed from the front. Think of it as  a line of people waiting for a bus. The person who is at the beginning of the line is the first one to enter the bus.   Basic features of Queue Like a stack, the queue is also an ordered list of elements of similar data types. A queue is a FIFO( First in First Out ) structure. Once a new element is inserted into the Queue, all the elements inserted before the new element in the queue  must be removed, to remove the new element. In a simple queue, there is a disadvantage after deleting element we cannot insert the element in the queue because of insertion  is possible from the rear but deletion is performed from the front.                                           insertion                                     ------------------
Read more

Implementation of stack Using Array

By -
Implementation  of stack Using Array #include<stdio.h> void pop(); void push(); void display(); int i,n,ch=0,top,item,stack[50]; int main() {     printf("Enter the number of element in Stack:\t");     scanf("%d",&n);     top=-1;     printf("Stack Operations");     printf("\n1.Push\n2.Pop\n3.Display\n4.Exit\n");    do     {         printf("Enter the choice: ");         scanf("%d",&ch);         switch(ch)         {             case 1:push();                    break;             case 2:pop();                    break;             case 3:display();                    break;             case 4:exit(0);                    break;             default:printf("!!Wrong choice!!\n");         }     }     while(ch!=4);     return 0; } void push(int item) {     if(top==n-1)         printf("Overflow\n");     else     {        
Read more