#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define MAX_LEN 100
char NFA_FILE[MAX_LEN];
char buffer[MAX_LEN];
int zz = 0;
// Structure to store DFA states and their
// status ( i.e new entry or already present)
struct DFA {
 char *states;
 int count;
} dfa;
int last_index = 0;
FILE *fp;
int symbols;
/* reset the hash map*/
void reset(int ar[], int size) {
 int i;
 // reset all the values of
 // the mapping array to zero
 for (i = 0; i < size; i++) {
 ar[i] = 0;
 }
}
// Check which States are present in the e-closure
/* map the states of NFA to a hash set*/
void check(int ar[], char S[]) {
 int i, j;
 // To parse the individual states of NFA
 int len = strlen(S);
 for (i = 0; i < len; i++) {
 // Set hash map for the position
 // of the states which is found
 j = ((int)(S[i]) - 65);
 ar[j]++;
 }
}
// To find new Closure States
void state(int ar[], int size, char S[]) {
 int j, k = 0;
 // Combine multiple states of NFA
 // to create new states of DFA
 for (j = 0; j < size; j++) {
 if (ar[j] != 0)
 S[k++] = (char)(65 + j);
 }
 // mark the end of the state
 S[k] = '\0';
}
// To pick the next closure from closure set
int closure(int ar[], int size) {
 int i;
 // check new closure is present or not
 for (i = 0; i < size; i++) {
 if (ar[i] == 1)
 return i;
 }
 return (100);
}
// Check new DFA states can be
// entered in DFA table or not
int indexing(struct DFA *dfa) {
 int i;
 for (i = 0; i < last_index; i++) {
 if (dfa[i].count == 0)
 return 1;
 }
 return -1;
}
/* To Display epsilon closure*/
void Display_closure(int states, int closure_ar[],
 char *closure_table[],
 char *NFA_TABLE[][symbols + 1],
 char *DFA_TABLE[][symbols]) {
 int i;
 for (i = 0; i < states; i++) {
 reset(closure_ar, states);
 closure_ar[i] = 2;
 // to neglect blank entry
 if (strcmp(&NFA_TABLE[i][symbols], "-") != 0) {
 // copy the NFA transition state to buffer
 strcpy(buffer, &NFA_TABLE[i][symbols]);
 check(closure_ar, buffer);
 int z = closure(closure_ar, states);
 // till closure get completely saturated
 while (z != 100)
 {
 	
 if (strcmp(&NFA_TABLE[z][symbols], "-") != 0) {
 strcpy(buffer, &NFA_TABLE[z][symbols]);
 // call the check function
 check(closure_ar, buffer);
 }
 closure_ar[z]++;
 z = closure(closure_ar, states);
 }
 }
 // print the e closure for every states of NFA
 printf("\n e-Closure (%c) :\t", (char)(65 + i));
 bzero((void *)buffer, MAX_LEN);
 state(closure_ar, states, buffer);
 strcpy(&closure_table[i], buffer);
 printf("%s\n", &closure_table[i]);
 }
}
/* To check New States in DFA */
int new_states(struct DFA *dfa, char S[]) {
 int i;
 // To check the current state is already
 // being used as a DFA state or not in
 // DFA transition table
 for (i = 0; i < last_index; i++) {
 if (strcmp(&dfa[i].states, S) == 0)
 return 0;
 }
 // push the new
 strcpy(&dfa[last_index++].states, S);
 // set the count for new states entered
 // to zero
 dfa[last_index - 1].count = 0;
 return 1;
}
// Transition function from NFA to DFA
// (generally union of closure operation )
void trans(char S[], int M, char *clsr_t[], int st,char *NFT[][symbols + 1], char TB[]) {
 int len = strlen(S);
 int i, j, k, g;
 int arr[st];
 int sz;
 reset(arr, st);
 char temp[MAX_LEN], temp2[MAX_LEN];
 char *buff;
 // Transition function from NFA to DFA
 for (i = 0; i < len; i++) {
 j = ((int)(S[i] - 65));
 strcpy(temp, &NFT[j][M]);
 if (strcmp(temp, "-") != 0) {
 sz = strlen(temp);
 g = 0;
 while (g < sz) {
 k = ((int)(temp[g] - 65));
 strcpy(temp2, &clsr_t[k]);
 check(arr, temp2);
 g++;
 }
 }
 }
 bzero((void *)temp, MAX_LEN);
 state(arr, st, temp);
 if (temp[0] != '\0') {
 strcpy(TB, temp);
 } else
 strcpy(TB, "-");
}
/* Display DFA transition state table*/
void Display_DFA(int last_index, struct DFA *dfa_states,
 char *DFA_TABLE[][symbols]) {
 int i, j;
 printf("\n\n**\n\n");
 printf("\t\t DFA TRANSITION STATE TABLE \t\t \n\n");
 printf("\n STATES OF DFA :\t\t");
 for (i = 1; i < last_index; i++)
 printf("%s, ", &dfa_states[i].states);
  printf("\n");
 printf("\n GIVEN SYMBOLS FOR DFA: \t");
 for (i = 0; i < symbols; i++)
 printf("%d, ", i);
 printf("\n\n");
 printf("STATES\t");
 for (i = 0; i < symbols; i++)
 printf("|%d\t", i);
 printf("\n");
 // display the DFA transition state table
 printf("--------+-----------------------\n");
 for (i = 0; i < zz; i++) {
 printf("%s\t", &dfa_states[i + 1].states);
 for (j = 0; j < symbols; j++) {
 printf("|%s \t", &DFA_TABLE[i][j]);
 }
 printf("\n");
 }
}
// Driver Code
int main() {
 int i, j, states;
 char T_buf[MAX_LEN];
 // creating an array dfa structures
 struct DFA *dfa_states = malloc(MAX_LEN * (sizeof(dfa)));
 states = 6, symbols = 2;
 printf("\n STATES OF NFA :\t\t");
 for (i = 0; i < states; i++)
 printf("%c, ", (char)(65 + i));
 printf("\n");
 printf("\n GIVEN SYMBOLS FOR NFA: \t");
 for (i = 0; i < symbols; i++)
 printf("%d, ", i);
 printf("eps");
 printf("\n\n");
char *NFA_TABLE[states][symbols + 1];
 // Hard coded input for NFA table
 char *DFA_TABLE[MAX_LEN][symbols];
 strcpy(&NFA_TABLE[0][0], "FC");
 strcpy(&NFA_TABLE[0][1], "-");
 strcpy(&NFA_TABLE[0][2], "BF");
 strcpy(&NFA_TABLE[1][0], "-");
 strcpy(&NFA_TABLE[1][1], "C");
 strcpy(&NFA_TABLE[1][2], "-");
 strcpy(&NFA_TABLE[2][0], "-");
 strcpy(&NFA_TABLE[2][1], "-");
 strcpy(&NFA_TABLE[2][2], "D");
 strcpy(&NFA_TABLE[3][0], "E");
 strcpy(&NFA_TABLE[3][1], "A");
 strcpy(&NFA_TABLE[3][2], "-");
 strcpy(&NFA_TABLE[4][0], "A");
 strcpy(&NFA_TABLE[4][1], "-");
 strcpy(&NFA_TABLE[4][2], "BF");
 strcpy(&NFA_TABLE[5][0], "-");
 strcpy(&NFA_TABLE[5][1], "-");
 strcpy(&NFA_TABLE[5][2], "-");
 printf("\n NFA STATE TRANSITION TABLE \n\n\n");
 printf("STATES\t");
 for (i = 0; i < symbols; i++)
 printf("|%d\t", i);
 printf("eps\n");
 // Displaying the matrix of NFA transition table
 printf("--------+------------------------------------\n");
 for (i = 0; i < states; i++) {
 printf("%c\t", (char)(65 + i));
 for (j = 0; j <= symbols; j++) {
 printf("|%s \t", &NFA_TABLE[i][j]);
 }
 printf("\n");
 }
 int closure_ar[states];
 char *closure_table[states];
 Display_closure(states, closure_ar, closure_table, NFA_TABLE, DFA_TABLE);
 strcpy(&dfa_states[last_index++].states, "-");
 dfa_states[last_index - 1].count = 1;
 bzero((void *)buffer, MAX_LEN);
 strcpy(buffer, &closure_table[0]);
 strcpy(&dfa_states[last_index++].states, buffer);
 int Sm = 1, ind = 1;
 int start_index = 1;
 // Filling up the DFA table with transition values
 // Till new states can be entered in DFA table
 while (ind != -1) {
 dfa_states[start_index].count = 1;
 Sm = 0;
 for (i = 0; i < symbols; i++) {
 trans(buffer, i, closure_table, states, NFA_TABLE, T_buf);
 // storing the new DFA state in buffer
 strcpy(&DFA_TABLE[zz][i], T_buf);
 // parameter to control new states
 Sm = Sm + new_states(dfa_states, T_buf);
 }
 ind = indexing(dfa_states);
 if (ind != -1)
 strcpy(buffer, &dfa_states[++start_index].states);
 zz++;
 }
 // display the DFA TABLE
 Display_DFA(last_index, dfa_states, DFA_TABLE);
 return 0;
}