In Ocaml:

Write:

n$\_$to$\_$d n

Type: $(\text{'}$q$,\text{'}$s$)$nfa$\_$t $->(\text{'}$q list, $\text{'}$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$.$

YOU MAY NOT USE ANY IMPERATIVE FUNCTIONS.

THIS INCLUDES REFERENCES, FOR AND WHILE LOOPS.

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: $(\text{'}$q$,\text{'}$s$)$nfa$\_$t $->(\text{'}$q list, $\text{'}$s$)$nfa$\_$t $->\text{'}$q list list $->(\text{'}$q list, $\text{'}$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 the previous three functions as helpers. They can be used to update the DFA's states, transitions, and final states.

Below is a list of all functions and types already written that you have access to:

type $(\text{'}$q$,\text{'}$s$)$transi $=\text{'}$q $*\text{'}$s option $*\text{'}$q

type $(\text{'}$q$,\text{'}$s$)$nfa$\_$y $=\{$sigma : $\text{'}$s list; qs : $\text{'}$q list; q$0$: $\text{'}$q; fs : $\text{'}$q list; delta : $(\text{'}$q$,\text{'}$s$)$transi list; $\}$

So: let nfa $=\{$sigma $=[\text{'}$z$\text{'}]$; qs $=[1$; $2$; $3]$; q$0=1$; fs $=[3]$; delta $=[(1,$Some $\text{'}$z$\text{'},2)$; $(2,$None$,3)]\}$

let dfa $=\{$sigma $=[\text{'}$z$\text{'}$; $\text{'}$y$\text{'}$; $\text{'}$x$\text{'}]$; qs $=[1$; $2$; $3]$; q$0=1$; fs $=[3]$; delta $=[(1,$Some $\text{'}$z$\text{'},2)$; $(2,$Some $\text{'}$y$\text{'},1)$; $(2,$Some $\text{'}$x$\text{'},3)]\}$;;

mo n ql t$,$of Type: $(\text{'}$q$,\text{'}$s$)$nfa$\_$y $->\text{'}$q list $->\text{'}$s option $->\text{'}$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 $\text{'}$z$\text{'})=[2]$

mo nfa $[2]($Some $\text{'}$z$\text{'})=[]$

mo nfa $[3]($Some $\text{'}$z$\text{'})=[]$

mo nfa $[1$;$2]($Some $\text{'}$z$\text{'})=[2]$

mo nfa $[2]$None $=[3]$

e$\_$clo n ql$,$of Type: $(\text{'}$q$,\text{'}$s$)$nfa$\_$y $->\text{'}$q list $->\text{'}$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: $(\text{'}$q$,$char$)$nfa$\_$y $->$string $->$bool$,$ which takes an NFA nfa and a string s$,$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;;

stateFresh n qt$,$of Type: $(\text{'}$q$,\text{'}$s$)$nfa$\_$t $->\text{'}$q list $->\text{'}$q list list, which takes an NFA and a list of states and outputs a list of state lists. Each element in the returned list is the list you can get to by starting from any state in the inputted list and moving on one character of the alphabet $($sigma$)$followed by any number of epsilon transitions.

So: stateFresh nfa $[1]=[[2$; $3]]$;;

stateFresh dfa $[1$; $2]=[[2]$; $[1]$; $[3]]$;;

stateFresh dfa $[2$; $3]=[[]$; $[1]$; $[3]]$;;

transFresh n qt$,$of Type: $(\text{'}$q$,\text{'}$s$)$nfa$\_$t $->\text{'}$q list $->(\text{'}$q list, $\text{'}$s$)$transition list, takes an NFA and a list of statesand returns list of transitions. Each element in the returned list is a tuple in the form of $($src$,$char$,$ dest$),$where dest is the list of states you can get to after starting from any state in the inputted list and moving on one character of the alphabet $($sigma$),$followed by any number of epsilon transitions.

So: transFresh nfa $[1]=[([1],$Some $\text{'}$z$\text{'},[2$; $3])]$

transFresh dfa $[1$; $2]=[([1$; $2],$Some $\text{'}$z$\text{'},[2])$; $([1$; $2],$Some $\text{'}$y$\text{'},[1])$; $([1$; $2],$Some $\text{'}$x$\text{'},[3])]$

transFresh dfa $[2$; $3]=[([2$; $3],$Some $\text{'}$z$\text{'},[])$; $([2$; $3],$Some $\text{'}$y$\text{'},[1])$; $([2$; $3],$Some $\text{'}$x$\text{'},[3])]$

finalFresh n qt$,$of Type: $(\text{'}$q$,\text{'}$s$)$nfa$\_$t $->\text{'}$q list $->\text{'}$q list list, takes an NFA and a list of states, return $[$qt$]$if an element of qt is a final state in the given NFA. Return $[]$otherwise$.$

So: finalFresh dfa $[1$; $2$; $3]=[[1$; $2$; $3]]$

finalFresh dfa $[1$; $2]=[]$