In Ocaml: Write: n_to_d n Type: ('q, 's) nfat -> ('q list, 's) nfa_t which takes an input NFA and converts it to an equivalent DFA. Assume that, for all NFAS nfa and for all strings s, accept nfa s = accept (nfa_to_dfa nfa) s. NO IMPERATIVES (except for fresh). THIS INCLUDES REFERENCES, FOR AND WHILE LOOPS, AND HASHMAPS Suggestions The n_to_d algorithm is pretty substantial. While you are free to design it in whatever manner you like, we suggest you consider writing a helper function n_to_d_step. Efficiency matters here, and if your code times out, it will fail the tests. Try to minimize the calls to List and set to prevent this. We time out at 5 minutes. OPTIONAL: Skip if you feel you have a better implementation n_to_d_step n d wrk Type: ('q, 's) nfat -> ('q list, 's) nfat -> 'q list list -> ('q list, 's) nfa_t Description: First, let's take a look at what is being passed into the function for clarity: Parameters nfa: the NFA to be converted into a DFA. dfa: the DFA to be created from the NFA. This will act as the accumulator in the function. Each time this function is called, the DFA should be updated based on the worklist. wrk: a list of unvisited states. Given an NFA, a partial DFA, and a worklist, this function will compute one step of the subset construction algorithm. This means that we take an unvisited DFA state from the worklist and add it to our DFA that we are creating (updating the list of all states, transitions, and final states appropriately). Our worklist is then updated for the next iteration by removing the newly processed state. You will want to use finalFresh, transFresh and startFresh as helpers. They can be used to update the DFA's states, transitions, and final states. Avalible functions and types type ('q, 's) transi = 'q * 's option 'q type ('q, 's) nfa_y = { sigma : 's list; qs : 'q list; që : 'q; fs : 'q list; delta : ('q, 's) transi list; } So: let nfa = { sigma = ['z']; qs = [1; 2; 3]; q0 = 1; fs = [3]; delta = [(1, Some 'z', 2); (2, None, 3)] } let dfa = {sigma = ['z'; 'y'; 'x']; qs = [1; 2; 3]; q0 = 1; fs = [3]; delta = [(1, Some 'z', 2); (2, Some 'y', 1); (2, Some 'x', 3)]};; mon ql t, of Type: ('q, 's) nfa_y -> 'q list -> 's option -> 'q list, takes an NFA n, a set of initial states ql, and a symbol option t. It returns a set of states that the NFA might be in after starting from any state in ql and making one transition on the symbol t. So: mo nfa [1] (Some 'z') = [2] mo nfa [2] (Some 'z') = [] mo nfa [3] (Some 'z') = [] mo nfa [1;2] (Some 'z') = [2] mo nfa [2] None = [3] e_clo n ql, of Type: ('q, 's) nfa_y -> 'q list -> 'q list, takes an NFA n and a set of initial states ql. It returns a set of states that the NFA might be in after making zero or more epsilon transitions from any state in ql. So: e_clo nfa [1] = [1] e_clo nfa [2] = [2;3] e_clo nfa [3] = [3] e_clo nfa [1;2] = [1;2;3] acce n t, of Type: ('q, char) nfa_y -> string -> bool, which takes an NFA nfa and a strings, and returns true if the NFA accepts the string. So: acce dfa = false; ; (* dfa_ex is the NFA defined above *) acce dfa "zx" = true;; acce dfa "zyx" = false;; acce dfa "zyzx" = true;;