SHARE
TWEET

Untitled

a guest Sep 20th, 2019 147 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. /*
  2.  * File: nfa.h
  3.  * Creator: George Ferguson
  4.  * Created: Thu Sep  1 17:54:41 2016
  5.  * Time-stamp: <Tue Aug  8 11:45:49 EDT 2017 ferguson>
  6.  */
  7.  
  8. #ifndef _nfa_h
  9. #define _nfa_h
  10.  
  11. #include <stdbool.h>
  12. #include "Set.h"
  13. #include "LinkedList.h"
  14. #include "LinkedList.h"
  15.  
  16. /**
  17.  * The data structure used to represent a nondeterministic finite automaton.
  18.  * @see FOCS Section 10.3
  19.  * @see Comments for DFA in dfa.h
  20.  */
  21. typedef struct NFA NFA;
  22.  
  23. /**
  24.  * Allocate and return a new NFA containing the given number of states.
  25.  */
  26. extern NFA new_NFA(NFA Q, int nstates);
  27.  
  28. extern bool NFA_execute2(NFA nfa, char *input);
  29. /**
  30.  * Free the given NFA.
  31.  */
  32. extern void NFA_free(NFA nfa);
  33.  
  34. /**
  35.  * Return the number of states in the given NFA.
  36.  */
  37. extern int NFA_get_size(NFA nfa);
  38.  
  39. /**
  40.  * Return the set of next states specified by the given NFA's transition
  41.  * function from the given state on input symbol sym.
  42.  */
  43. extern Set NFA_get_transitions(NFA nfa, int state, char sym);
  44.  
  45. /**
  46.  * For the given NFA, add the state dst to the set of next states from
  47.  * state src on input symbol sym.
  48.  */
  49. extern void NFA_add_transition(NFA nfa, int src, char sym, int dst,IntHashSet a[][128]);
  50.  
  51. /**
  52.  * Add a transition for the given NFA for each symbol in the given str.
  53.  */
  54. extern void NFA_add_transition_str(NFA nfa, int src, char *str, int dst);
  55.  
  56. /**
  57.  * Add a transition for the given NFA for each input symbol.
  58.  */
  59. extern void NFA_add_transition_all(NFA nfa, int src, int dst,IntHashSet a[][128]);
  60.  
  61. /**
  62.  * Set whether the given NFA's state is accepting or not.
  63.  */
  64. extern void NFA_set_accepting(NFA nfa, int state, bool value);
  65.  
  66. /**
  67.  * Return true if the given NFA's state is an accepting state.
  68.  */
  69. extern bool NFA_get_accepting(NFA nfa, int state);
  70.  
  71. /**
  72.  * Run the given NFA on the given input string, and return true if it accepts
  73.  * the input, otherwise false.
  74.  */
  75. extern bool NFA_execute(NFA nfa, char *input, IntHashSet a[][128]);
  76.  
  77. /**
  78.  * Print the given NFA to System.out.
  79.  */
  80. extern void NFA_print(NFA nfa);
  81.  
  82.  
  83. typedef struct NFA {
  84.  
  85. int States; //number of states
  86. int finStates; // number of accepting states
  87. int counter; //tracks which state it is right now
  88.  
  89.  
  90.  
  91.  
  92. } NFA;
  93.  
  94.  
  95. extern NFA new_NFA(NFA Q, int nstates){ //rows columns for the transition array
  96.  
  97. NFA* Qp=&Q;
  98. Qp->States=nstates;
  99.  
  100.  
  101.  
  102. return Q;
  103. }
  104.  
  105.  
  106.  
  107.  
  108. extern void NFA_add_transition_all(NFA nfa, int src, int dst,  IntHashSet a[][128]){
  109.  
  110.     for(int i=0;i<128;i++){
  111.  
  112.      IntHashSet_insert(a[src][i], dst); // equivalent to arr[src][i]=dst
  113.  
  114.     }
  115.  
  116. //
  117.  
  118. }
  119.  
  120.  
  121. extern void NFA_add_transition(NFA nfa, int src, char sym, int dst, IntHashSet a[][128]){
  122.  
  123.      //equivalent to arr[src][sym]=dst. but this is using pointer arithmetic
  124.      IntHashSet_insert(a[src][sym], dst);
  125.     printf("is it reaching for ffs");
  126.  
  127. }
  128.  
  129. extern void NFA_add_transition_except(NFA nfa, int src, char sym, int dst, IntHashSet a[][128]);
  130.  
  131. extern void NFA_add_transition_except(NFA nfa, int src, char sym, int dst, IntHashSet a[][128]){
  132.  
  133.      //equivalent to arr[src][sym]=dst. but this is using pointer arithmetic
  134.      for(int i=0;i<128;i++){
  135.     if(i!=sym){
  136.      IntHashSet_insert(a[src][i], dst); // equivalent to arr[src][i]=dst
  137.     }
  138.     }
  139. }
  140.  
  141.  
  142.  
  143.  
  144.  
  145.  
  146.  
  147.  
  148.  
  149. extern bool NFA_execute(NFA nfa, char *input, IntHashSet a[][128]){
  150.  
  151.     IntHashSet set1 = new_IntHashSet(100);
  152.     IntHashSet set2 = new_IntHashSet(100);
  153.     IntHashSet_insert(set1, 0);
  154.  
  155.  
  156.     for(int i=0; input[i]!='\0';i++){ //loops through the input, and changes the current state according to the transition table
  157.    
  158.      
  159.     IntHashSetIterator iterator = IntHashSet_iterator(set1);
  160.     while (IntHashSetIterator_hasNext(iterator)) {
  161.         int element = IntHashSetIterator_next(iterator); //extracting the element from the hashset, which corresponds to the possible transition on the character input[i]
  162.  
  163.         //put the linked list(the list of possible transition of input[i] in a linked list called temp
  164.  
  165.  
  166.  
  167.          IntHashSetIterator iterator2 = IntHashSet_iterator(a[element][input[i]]);
  168.                     while (IntHashSetIterator_hasNext(iterator2)) {
  169.                               int data =  IntHashSetIterator_next(iterator2);//loop through temp
  170.                     printf("the hashset of letter %c, at state %i", input[i], element);
  171.  
  172.  
  173.                         printf("\n the value that will be added is%i, the character is %c", data, input[i]);
  174.                             if(data!=5)IntHashSet_insert(set2, data); //add it to the hashset
  175.  
  176.  
  177.  
  178.     }
  179.  
  180.     free(iterator2);
  181.  
  182.  
  183.  
  184.  
  185. }
  186. free(iterator);
  187. IntHashSet_free(set1);
  188. IntHashSet set1 = new_IntHashSet(100);
  189. IntHashSet_union(set1, set2);
  190. /*IntHashSetIterator iterator3 = IntHashSet_iterator(a[1]['o']);
  191.     while (IntHashSetIterator_hasNext(iterator3)) {
  192.         int element = IntHashSetIterator_next(iterator3);
  193.         printf("\n \n checking the set 1 %d ", element);
  194.     } free(iterator3);*/
  195. IntHashSet_free(set2);
  196.  
  197.  
  198.  
  199.  
  200. }
  201. bool d= false;
  202. //after everything, we loop through our set1, if it has the accepting state, we accept the string.
  203. IntHashSetIterator iterator4 = IntHashSet_iterator(set1);
  204.     while (IntHashSetIterator_hasNext(iterator4)) {
  205.  
  206.         int element = IntHashSetIterator_next(iterator4);
  207.     printf("\n current states are element %i", element);
  208.         if (element==nfa.finStates) d=true;
  209.     }
  210.  
  211.     free(iterator4);
  212.  
  213.     IntHashSet_free(set1);
  214.  
  215.  
  216.  
  217.     free(input);
  218.  
  219.  
  220. return d;
  221. }
  222.  
  223.  
  224.  
  225. /*extern bool NFA_execute2(NFA nfa, char *input){
  226.  
  227.     IntHashSet set3 = new_IntHashSet(100);
  228.     IntHashSet set4 = new_IntHashSet(100);
  229.     IntHashSet_insert(set3, 0);
  230.  
  231.  
  232.     for(int i=0; input[i]!='\0';i++){ //loops through the input, and changes the current state according to the transition table
  233.  
  234.     IntHashSetIterator iterator = IntHashSet_iterator(set3);
  235.     while (IntHashSetIterator_hasNext(iterator)) {
  236.         int element = IntHashSetIterator_next(iterator); //extracting the element from the hashset, which corresponds to the possible transition on the character input[i]
  237.  
  238.         //put the linked list(the list of possible transition of input[i] in a linked list called temp
  239.  
  240.  
  241.  
  242.         LinkedListIterator iterator2 = LinkedList_iterator(*(nfa.ArrayP2 + (element*128 + input[i])));
  243.                     while (LinkedListIterator_hasNext(iterator2)) { //loop through temp
  244.                         void *data = LinkedListIterator_next(iterator2);
  245.                         char *str = (char*)data; //extracting the state that we transitioned to
  246.                         int val = atoi(str); //convert it to int so it can be added to the hashset
  247.  
  248.                         printf("\n the value that will be added is%i, the character is %c", val, input[i]);
  249.                       if(val!=-1)  IntHashSet_insert(set4, val); //add it to the hashset
  250.  
  251.  
  252.  
  253.     }
  254.  
  255.     free(iterator2);
  256.  
  257.  
  258.  
  259.  
  260. }
  261. free(iterator);
  262. IntHashSet_free(set3);
  263. IntHashSet set3 = new_IntHashSet(100);
  264. IntHashSet_union(set3, set4);
  265.  
  266. IntHashSet_free(set4);
  267. IntHashSet set4 = new_IntHashSet(100);
  268.  
  269.  
  270.  
  271. }
  272. bool d= false;
  273. //after everything, we loop through our set1, if it has the accepting state, we accept the string.
  274. IntHashSetIterator iterator = IntHashSet_iterator(set3);
  275.     while (IntHashSetIterator_hasNext(iterator)) {
  276.  
  277.         int element = IntHashSetIterator_next(iterator);
  278.     printf("\n current states are element %i", element);
  279.         if (element==nfa.finStates) d=true;
  280.     }
  281.  
  282.     free(iterator);
  283.  
  284.     IntHashSet_free(set3);
  285.  
  286.     IntHashSet_free(set4);
  287.  
  288.     free(input);
  289.  
  290.  
  291. return d;
  292. }*/
  293. #endif
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy. OK, I Understand
 
Top