Scribd
Upload
3 views5 pages

DFA Construction in C Programming

The document contains a C program that converts a nondeterministic finite automaton (NFA) into an equivalent deterministic finite automaton (DFA). It includes functions for inserting transitions, finding states, and printing the resulting DFA. The program prompts the user for input regarding the alphabet, states, transitions, and final states, then processes this information to display the DFA's structure.

Uploaded by

manuelsaju21
Copyright
© All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as DOCX, PDF, TXT or read online on Scribd
3 views5 pages

DFA Construction in C Programming

The document contains a C program that converts a nondeterministic finite automaton (NFA) into an equivalent deterministic finite automaton (DFA). It includes functions for inserting transitions, finding states, and printing the resulting DFA. The program prompts the user for input regarding the alphabet, states, transitions, and final states, then processes this information to display the DFA's structure.

Uploaded by

manuelsaju21
Copyright
© All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as DOCX, PDF, TXT or read online on Scribd

/*MANUEL SAJU */

/*S7 CSE B*/


/*ROLL NO:14*/

#include <stdio.h>
#include <stdlib.h>
struct node {
int st;
struct node *link;
};
struct node1 {
int nst[20];
};

void insert(int, char, int);


int findalpha(char);
void findfinalstate(void);
int insertdfastate(struct node1);
int compare(struct node1, struct node1);
void printnewstate(struct node1);

static int set[20], nostate, noalpha, s, notransition, nofinal, start,


finalstate[20], c, r,
buffer[20];
int complete = -1;
char alphabet[20];
static int eclosure[20][20] = {0};
struct node1 hash[20];
struct node *transition[20][20] = {NULL};

void main() {
int i, j, k, m, t, n, l;
struct node *temp;
struct node1 newstate = {0}, tmpstate = {0};

printf("NOTE:- [ use letter e as epsilon]\n");


printf("NOTE:- [e must be last character ,if it is present]\n");

printf("\nEnter Number of alphabets and alphabets : \n");


scanf("%d", &noalpha);

getchar();
for (i = 0; i < noalpha; i++) {
alphabet[i] = getchar();
getchar();
}

printf("Enter the number of states?\n");


scanf("%d", &nostate);

printf("Enter the start state?\n");


scanf("%d", &start);

ADI SHANKARA INSTITUTE OF ENGINEERING & TECHNOLOGY - 683


printf("Enter the number of final states?\n");
scanf("%d", &nofinal);

printf("Enter the final states?\n");


for (i = 0; i < nofinal; i++)
scanf("%d", &finalstate[i]);

printf("Enter no of transition?\n");
scanf("%d", &notransition);

printf("NOTE:- [Transition is in the form–> qno alphabet qno] %d


", notransition);
printf("NOTE:- [States number must be greater than zero]\n");
printf("\nEnter transition?\n");

for (i = 0; i < notransition; i++) {


scanf("%d%lc%d", &r, &c, &s);
insert(r, c, s);
}
for (i = 0; i < 20; i++) {
for (j = 0; j < 20; j++)
hash[i].nst[j] = 0;
}
complete = -1;
i = -1;
printf("\nEquivalent DFA...........\n");
printf("Transitions of DFA\n");

[Link][start] = start;
insertdfastate(newstate);

while (i != complete) {
i++;
newstate = hash[i];
for (k = 0; k < noalpha; k++) {
c = 0;
for (j = 1; j <= nostate; j++)
set[j] = 0;
for (j = 1; j <= nostate; j++) {
l = [Link][j];
if (l != 0) {
temp = transition[l][k];
while (temp != NULL) {
if (set[temp->st] == 0) {
c++;
set[temp->st] = temp->st;
}
temp = temp->link;
}
}
}
printf("\n");
if (c != 0) {
for (m = 1; m <= nostate; m++) [Link][m] = set[m];

insertdfastate(tmpstate);

ADI SHANKARA INSTITUTE OF ENGINEERING & TECHNOLOGY - 683


printnewstate(newstate);
printf("%c\t", alphabet[k]);
printnewstate(tmpstate);
printf("\n");
} else {
printnewstate(newstate);
printf("%c\t", alphabet[k]);
printf("NULL\n");
}
}
}
printf("\nStates of DFA:\n");
for (i = 0; i <= complete; i++) printnewstate(hash[i]);
printf("\n Alphabets:\n");
for (i = 0; i < noalpha; i++) printf("%c\t", alphabet[i]);
printf("\n Start State:\n");
printf("q%d", start);
printf("\nFinal states:\n");
findfinalstate();

int insertdfastate(struct node1 newstate) {


int i;
for (i = 0; i <= complete; i++) {
if (compare(hash[i], newstate))
return 0;
}
complete++;
hash[complete] = newstate;
return 1;
}

int compare(struct node1 a, struct node1 b) {


int i;

for (i = 1; i <= nostate; i++) {


if ([Link][i] != [Link][i])
return 0;
}
return 1;
}

void insert(int r, char c, int s) {


int j;
struct node *temp;
j = findalpha(c);
if (j == 999) {
printf("error\n");
exit(0);
}
temp = (struct node *)malloc(sizeof(struct node));
temp->st = s;
temp->link = transition[r][j];
transition[r][j] = temp;

ADI SHANKARA INSTITUTE OF ENGINEERING & TECHNOLOGY - 683


}

int findalpha(char c) {
int i;
for (i = 0; i < noalpha; i++)
if (alphabet[i] == c)
return i;

return (999);
}

void findfinalstate() {
int i, j, k, t;

for (i = 0; i <= complete; i++) {


for (j = 1; j <= nostate; j++) {
for (k = 0; k < nofinal; k++) {
if (hash[i].nst[j] == finalstate[k]) {
printnewstate(hash[i]); printf("\
t");
j = nostate;
break;
}
}
}
}
}

void printnewstate(struct node1 state) {


int j;
printf("{");
for (j = 1; j <= nostate; j++) {
if ([Link][j] != 0) printf("q%d,", [Link][j]);
}
printf("}\t");
}

ADI SHANKARA INSTITUTE OF ENGINEERING & TECHNOLOGY - 683


ADI SHANKARA INSTITUTE OF ENGINEERING & TECHNOLOGY - 683

Common questions

Powered by AI

The function 'insert' handles state transitions by first determining the index of the given alphabet in the predefined list of alphabets using the 'findalpha' function. It then creates a new node representing the transition, assigning the destination state and linking it in the transition list. The transition is executed by linking the new node into the transition table for the specified source state and alphabet combination .

The comparison of states is necessary to ensure that each newly created DFA state is unique and not a duplication of an existing state. This is crucial for maintaining the efficiency and correctness of the DFA. By comparing possible new state sets with those already in the hash, it prevents unnecessary redundancies and ensures that only new and unique state combinations are added to the DFA's state set .

Final states of the DFA are determined by examining the states of the DFA to see if they contain any of the NFA's final states. This is done by iterating over the DFA states and checking if at least one of the states within a DFA state is one of the NFA's final states. If it is, that state is marked as a final state in the DFA .

The function 'findalpha' finds the position of a given alphabet within a predefined array of alphabets. This position is crucial as it determines the index to be used in the transition table, allowing the program to correctly associate the input alphabet with its corresponding transitions .

The program ensures that all potential transitions are checked by iterating over each DFA state and for each alphabet in the transition process. It checks all transitions that can happen from the current combination of NFA states, tracking possible new states resulting from these transitions. Each of these possible new states is stored and analyzed, ensuring comprehensive coverage of all alphabet-based transitions for every state .

The document implies handling epsilon ('ε') transitions by treating them as special cases where the transition doesn't involve consuming an input symbol. These transitions are used to find reachable states from any NFA state without consuming alphabet symbols. For the conversion process, epsilon-closure is computed, which includes any state that can be reached from a given state following epsilon-transitions only. Epsilon closures simplify the formation of DFA states by including all reachable states without explicit transitions in the NFA .

The document addresses input validation by using functions like 'findalpha' to ensure if the given input alphabet has a corresponding entry in the predefined list of alphabets. If an invalid alphabet (not present in the list) is encountered, the program issues an error message and terminates to avoid executing invalid transitions. This guards against attempts to use undefined symbols in transition definitions .

The process to convert an NFA to a DFA involves several steps. Firstly, define all alphabets and states, including the start and final states. For each state and alphabet, create a transition function that maps the current state and given alphabet to a set of resultant states in the NFA. Next, construct the equivalent DFA by creating new states using combinations of these S (set of NFA states) as necessary, initialized with the start state of the NFA. Continuously add new DFA states if they do not already exist, each representing a combination of NFA states, until no more unique states are generated. Store these states and define the transitions accordingly .

The 'hash' array in the document stores all possible states of the DFA, where each element represents a set of NFA states that combine to form a DFA state. It is used to track which state combinations have already been processed and which new states need to be handled during the conversion process. This ensures that each unique combination of NFA states is only processed once, preventing redundant transitions and state calculations in the DFA construction .

The variable 'complete' serves as an index to track the last processed state in the list of DFA states stored in the 'hash' array. It represents the count of unique DFA states discovered so far. The while loop in the conversion process continues adding new states until all possible DFA states are processed, which is when the index equals the total number of states .

You might also like