Advertisement
Nahid8195

DFA Implement of (A|B)*ABB

Dec 9th, 2022
885
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C 1.63 KB | None | 0 0
  1. #include <stdio.h>
  2. #define TOTAL_STATES 4
  3. #define FINAL_STATES 1
  4. #define ALPHABET_CHARCTERS 2
  5. #define UNKNOWN_SYMBOL_ERR 0
  6. #define NOT_REACHED_FINAL_STATE 1
  7. #define REACHED_FINAL_STATE 2
  8. enum DFA_STATES {q0,q1, q2, q3};
  9. enum input {a,b};
  10.  
  11. int Accepted_states[FINAL_STATES]= {q3};
  12. char alphabet[ALPHABET_CHARCTERS]= {'a','b'};
  13. int Transition_Table[TOTAL_STATES][ALPHABET_CHARCTERS];
  14. int Current_state=q0;
  15.  
  16. void DefineDFA()
  17. {
  18. Transition_Table[q0][a] = q1;
  19. Transition_Table[q0][b] = q0;
  20. Transition_Table[q1][a] = q1;
  21. Transition_Table[q1][b] = q2;
  22. Transition_Table[q2][a] = q1;
  23. Transition_Table[q2][b] = q3;
  24. Transition_Table[q3][a] = q0;
  25. Transition_Table[q3][b] = q1;
  26. }
  27.  
  28. int DFA(char current_symbol)
  29. {
  30. int i,pos;
  31. for(pos=0; pos<ALPHABET_CHARCTERS; pos++)
  32. if(current_symbol==alphabet[pos])
  33. break;//stops if any character other than a or b
  34. if(pos==ALPHABET_CHARCTERS)
  35. return UNKNOWN_SYMBOL_ERR;
  36. for(i=0; i<FINAL_STATES; i++)
  37. if((Current_state=Transition_Table[Current_state][pos])==Accepted_states[i])
  38. return REACHED_FINAL_STATE;
  39. return NOT_REACHED_FINAL_STATE;
  40. }
  41.  
  42. int main(void)
  43. {
  44. char current_symbol;
  45. int result;
  46.  
  47. DefineDFA();    //Fill transition table
  48.  
  49. printf("Enter a string with 'a' s and 'b's:\nPress Enter Key to stop\n");
  50.  
  51.  
  52. while((current_symbol=getchar())!= '\n')
  53. if((result= DFA(current_symbol))==UNKNOWN_SYMBOL_ERR)
  54. break;
  55. switch (result)
  56. {
  57. case UNKNOWN_SYMBOL_ERR:
  58. printf("Unknown Symbol %c",current_symbol);
  59. break;
  60. case NOT_REACHED_FINAL_STATE:
  61. printf("Not accepted");
  62. break;
  63. case REACHED_FINAL_STATE:
  64. printf("Accepted");
  65. break;
  66. default:
  67. printf("Unknown Error");
  68. }
  69. printf("\n\n\n");
  70. return 0;
  71. }
  72.  
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement