fork download
copy 
  1. #include <stdio.h>
  2. #include <stdlib.h>
  3. #include <string.h>
  4. #define MAX_LEN 100
  5.  
  6. char NFA_FILE[MAX_LEN];
  7. char buffer[MAX_LEN];
  8. int zz = 0;
  9.  
  10. // Structure to store DFA states and their
  11. // status ( i.e new entry or already present)
  12. struct DFA {
  13.   char *states;
  14.   int count;
  15. } dfa;
  16.  
  17. int last_index = 0;
  18. FILE *fp;
  19. int symbols;
  20.  
  21. /* reset the hash map*/
  22. void reset(int ar[], int size) {
  23.   int i;
  24.  
  25.   // reset all the values of
  26.   // the mapping array to zero
  27.   for (i = 0; i < size; i++) {
  28.     ar[i] = 0;
  29.   }
  30. }
  31.  
  32. // Check which States are present in the e-closure
  33.  
  34. /* map the states of NFA to a hash set*/
  35. void check(int ar[], char S[]) {
  36.   int i, j;
  37.  
  38.   // To parse the individual states of NFA
  39.   int len = strlen(S);
  40.   for (i = 0; i < len; i++) {
  41.  
  42.     // Set hash map for the position
  43.     // of the states which is found
  44.     j = ((int)(S[i]) - 65);
  45.     ar[j]++;
  46.   }
  47. }
  48.  
  49. // To find new Closure States
  50. void state(int ar[], int size, char S[]) {
  51.   int j, k = 0;
  52.  
  53.   // Combine multiple states of NFA
  54.   // to create new states of DFA
  55.   for (j = 0; j < size; j++) {
  56.     if (ar[j] != 0)
  57.       S[k++] = (char)(65 + j);
  58.   }
  59.  
  60.   // mark the end of the state
  61.   S[k] = '\0';
  62. }
  63.  
  64. // To pick the next closure from closure set
  65. int closure(int ar[], int size) {
  66.   int i;
  67.  
  68.   // check new closure is present or not
  69.   for (i = 0; i < size; i++) {
  70.     if (ar[i] == 1)
  71.       return i;
  72.   }
  73.   return (100);
  74. }
  75.  
  76. // Check new DFA states can be
  77. // entered in DFA table or not
  78. int indexing(struct DFA *dfa) {
  79.   int i;
  80.  
  81.   for (i = 0; i < last_index; i++) {
  82.     if (dfa[i].count == 0)
  83.       return 1;
  84.   }
  85.   return -1;
  86. }
  87.  
  88. /* To Display epsilon closure*/
  89. void Display_closure(int states, int closure_ar[],
  90.                      char *closure_table[],
  91.                      char *NFA_TABLE[][symbols + 1],
  92.                      char *DFA_TABLE[][symbols]) {
  93.   int i;
  94.   for (i = 0; i < states; i++) {
  95.     reset(closure_ar, states);
  96.     closure_ar[i] = 2;
  97.  
  98.     // to neglect blank entry
  99.     if (strcmp(&NFA_TABLE[i][symbols], "-") != 0) {
  100.  
  101.       // copy the NFA transition state to buffer
  102.       strcpy(buffer, &NFA_TABLE[i][symbols]);
  103.       check(closure_ar, buffer);
  104.       int z = closure(closure_ar, states);
  105.  
  106.       // till closure get completely saturated
  107.       while (z != 100)
  108.       {
  109.         if (strcmp(&NFA_TABLE[z][symbols], "-") != 0) {
  110.           strcpy(buffer, &NFA_TABLE[z][symbols]);
  111.  
  112.           // call the check function
  113.           check(closure_ar, buffer);
  114.         }
  115.         closure_ar[z]++;
  116.         z = closure(closure_ar, states);
  117.       }
  118.     }
  119.  
  120.     // print the e closure for every states of NFA
  121.     printf("\n e-Closure (%c) :\t", (char)(65 + i));
  122.  
  123.     bzero((void *)buffer, MAX_LEN);
  124.     state(closure_ar, states, buffer);
  125.     strcpy(&closure_table[i], buffer);
  126.     printf("%s\n", &closure_table[i]);
  127.   }
  128. }
  129.  
  130. /* To check New States in DFA */
  131. int new_states(struct DFA *dfa, char S[]) {
  132.  
  133.   int i;
  134.  
  135.   // To check the current state is already
  136.   // being used as a DFA state or not in
  137.   // DFA transition table
  138.   for (i = 0; i < last_index; i++) {
  139.     if (strcmp(&dfa[i].states, S) == 0)
  140.       return 0;
  141.   }
  142.  
  143.   // push the new
  144.   strcpy(&dfa[last_index++].states, S);
  145.  
  146.   // set the count for new states entered
  147.   // to zero
  148.   dfa[last_index - 1].count = 0;
  149.   return 1;
  150. }
  151.  
  152. // Transition function from NFA to DFA
  153. // (generally union of closure operation )
  154. void trans(char S[], int M, char *clsr_t[], int st,
  155.                char *NFT[][symbols + 1], char TB[]) {
  156.   int len = strlen(S);
  157.   int i, j, k, g;
  158.   int arr[st];
  159.   int sz;
  160.   reset(arr, st);
  161.   char temp[MAX_LEN], temp2[MAX_LEN];
  162.   char *buff;
  163.  
  164.   // Transition function from NFA to DFA
  165.   for (i = 0; i < len; i++) {
  166.  
  167.     j = ((int)(S[i] - 65));
  168.     strcpy(temp, &NFT[j][M]);
  169.  
  170.     if (strcmp(temp, "-") != 0) {
  171.       sz = strlen(temp);
  172.       g = 0;
  173.  
  174.       while (g < sz) {
  175.         k = ((int)(temp[g] - 65));
  176.         strcpy(temp2, &clsr_t[k]);
  177.         check(arr, temp2);
  178.         g++;
  179.       }
  180.     }
  181.   }
  182.  
  183.   bzero((void *)temp, MAX_LEN);
  184.   state(arr, st, temp);
  185.   if (temp[0] != '\0') {
  186.     strcpy(TB, temp);
  187.   } else
  188.     strcpy(TB, "-");
  189. }
  190.  
  191. /* Display DFA transition state table*/
  192. void Display_DFA(int last_index, struct DFA *dfa_states,
  193.                  char *DFA_TABLE[][symbols]) {
  194.   int i, j;
  195.   printf("\n\n********************************************************\n\n");
  196.   printf("\t\t DFA TRANSITION STATE TABLE \t\t \n\n");
  197.   printf("\n STATES OF DFA :\t\t");
  198.  
  199.   for (i = 1; i < last_index; i++)
  200.     printf("%s, ", &dfa_states[i].states);
  201.   printf("\n");
  202.   printf("\n GIVEN SYMBOLS FOR DFA: \t");
  203.  
  204.   for (i = 0; i < symbols; i++)
  205.     printf("%d, ", i);
  206.   printf("\n\n");
  207.   printf("STATES\t");
  208.  
  209.   for (i = 0; i < symbols; i++)
  210.     printf("|%d\t", i);
  211.   printf("\n");
  212.  
  213.   // display the DFA transition state table
  214.   printf("--------+-----------------------\n");
  215.   for (i = 0; i < zz; i++) {
  216.     printf("%s\t", &dfa_states[i + 1].states);
  217.     for (j = 0; j < symbols; j++) {
  218.       printf("|%s \t", &DFA_TABLE[i][j]);
  219.     }
  220.     printf("\n");
  221.   }
  222. }
  223.  
  224. // Driver Code
  225. int main() {
  226.   int i, j, states;
  227.   char T_buf[MAX_LEN];
  228.  
  229.   // creating an array dfa structures
  230.   struct DFA *dfa_states = malloc(MAX_LEN * (sizeof(dfa)));
  231.   states = 6, symbols = 2;
  232.  
  233.   printf("\n STATES OF NFA :\t\t");
  234.   for (i = 0; i < states; i++)
  235.  
  236.     printf("%c, ", (char)(65 + i));
  237.   printf("\n");
  238.   printf("\n GIVEN SYMBOLS FOR NFA: \t");
  239.  
  240.   for (i = 0; i < symbols; i++)
  241.  
  242.     printf("%d, ", i);
  243.   printf("eps");
  244.   printf("\n\n");
  245.   char *NFA_TABLE[states][symbols + 1];
  246.  
  247.   // Hard coded input for NFA table
  248.   char *DFA_TABLE[MAX_LEN][symbols];
  249.   strcpy(&NFA_TABLE[0][0], "FC");
  250.   strcpy(&NFA_TABLE[0][1], "-");
  251.   strcpy(&NFA_TABLE[0][2], "BF");
  252.   strcpy(&NFA_TABLE[1][0], "-");
  253.   strcpy(&NFA_TABLE[1][1], "C");
  254.   strcpy(&NFA_TABLE[1][2], "-");
  255.   strcpy(&NFA_TABLE[2][0], "-");
  256.   strcpy(&NFA_TABLE[2][1], "-");
  257.   strcpy(&NFA_TABLE[2][2], "D");
  258.   strcpy(&NFA_TABLE[3][0], "E");
  259.   strcpy(&NFA_TABLE[3][1], "A");
  260.   strcpy(&NFA_TABLE[3][2], "-");
  261.   strcpy(&NFA_TABLE[4][0], "A");
  262.   strcpy(&NFA_TABLE[4][1], "-");
  263.   strcpy(&NFA_TABLE[4][2], "BF");
  264.   strcpy(&NFA_TABLE[5][0], "-");
  265.   strcpy(&NFA_TABLE[5][1], "-");
  266.   strcpy(&NFA_TABLE[5][2], "-");
  267.   printf("\n NFA STATE TRANSITION TABLE \n\n\n");
  268.   printf("STATES\t");
  269.  
  270.   for (i = 0; i < symbols; i++)
  271.     printf("|%d\t", i);
  272.   printf("eps\n");
  273.  
  274.   // Displaying the matrix of NFA transition table
  275.   printf("--------+------------------------------------\n");
  276.   for (i = 0; i < states; i++) {
  277.     printf("%c\t", (char)(65 + i));
  278.  
  279.     for (j = 0; j <= symbols; j++) {
  280.       printf("|%s \t", &NFA_TABLE[i][j]);
  281.     }
  282.     printf("\n");
  283.   }
  284.   int closure_ar[states];
  285.   char *closure_table[states];
  286.  
  287.   Display_closure(states, closure_ar, closure_table, NFA_TABLE, DFA_TABLE);
  288.   strcpy(&dfa_states[last_index++].states, "-");
  289.  
  290.   dfa_states[last_index - 1].count = 1;
  291.   bzero((void *)buffer, MAX_LEN);
  292.  
  293.   strcpy(buffer, &closure_table[0]);
  294.   strcpy(&dfa_states[last_index++].states, buffer);
  295.  
  296.   int Sm = 1, ind = 1;
  297.   int start_index = 1;
  298.  
  299.   // Filling up the DFA table with transition values
  300.   // Till new states can be entered in DFA table
  301.   while (ind != -1) {
  302.     dfa_states[start_index].count = 1;
  303.     Sm = 0;
  304.     for (i = 0; i < symbols; i++) {
  305.  
  306.       trans(buffer, i, closure_table, states, NFA_TABLE, T_buf);
  307.  
  308.       // storing the new DFA state in buffer
  309.       strcpy(&DFA_TABLE[zz][i], T_buf);
  310.  
  311.       // parameter to control new states
  312.       Sm = Sm + new_states(dfa_states, T_buf);
  313.     }
  314.     ind = indexing(dfa_states);
  315.     if (ind != -1)
  316.       strcpy(buffer, &dfa_states[++start_index].states);
  317.     zz++;
  318.   }
  319.   // display the DFA TABLE
  320.   Display_DFA(last_index, dfa_states, DFA_TABLE);
  321.  
  322.   return 0;
  323. }
Success #stdin #stdout 0.01s 5432KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
 STATES OF NFA :		A, B, C, D, E, F, 

 GIVEN SYMBOLS FOR NFA: 	0, 1, eps


 NFA STATE TRANSITION TABLE 


STATES	|0	|1	eps
--------+------------------------------------
A	|FC 	|- 	|BF 	
B	|- 	|C 	|- 	
C	|- 	|- 	|D 	
D	|E 	|A 	|- 	
E	|A 	|- 	|BF 	
F	|- 	|- 	|- 	

 e-Closure (A) :	ABF

 e-Closure (B) :	B

 e-Closure (C) :	CD

 e-Closure (D) :	D

 e-Closure (E) :	BEF

 e-Closure (F) :	F


********************************************************

		 DFA TRANSITION STATE TABLE 		 


 STATES OF DFA :		ABF, CDF, CD, BEF, 

 GIVEN SYMBOLS FOR DFA: 	0, 1, 

STATES	|0	|1	
--------+-----------------------
ABF	|CDF 	|CD 	
CDF	|BEF 	|ABF 	
CD	|BEF 	|ABF 	
BEF	|ABF 	|CD
https://ideone.com/9dOlaE
language:
C (gcc 8.3)
created:
1 year ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!