In Ocaml:

Implement:

Below are all the types and functions that are already implemented:

type regexp$\_$t $=$

$|$ Empty$\_$String

$|$ Char of char

$|$ Union of regexp$\_$t $*$ regexp$\_$t

$|$ Concat of regexp$\_$t $*$ regexp$\_$t

$|$ Star of regexp$\_$t

Empty$\_$String represents the regular expression recognizing the empty string $($not the empty set!$).$ Formally, the empty string can be represented as epsilon.

Char c represents the regular expression that accepts the single character c$.$ Written as a formal regular expression, this would be c$.$

Union $($r$1,$ r$2)$ represents the regular expression that is the union of r$1$ and r$2.$ For example, Union$($Char $\text{'}$a$\text{'},$ Char'b'$)$ is the same as the formal regular expression a$|$b$.$

Concat $($r$1,$ r$2)$ represents the concatenation of r$1$ followed by r$2.$ For example, Concat$($Char $\text{'}$a$\text{'},$ Char $\text{'}$b$\text{'})$ is the same as the formal regular expression ab$.$

Star r represents the Kleene closure of regular expression r$.$ For example, Star $($Union $($Char $\text{'}$a$\text{'},$ Char $\text{'}$b$\text{'}))$ is the same as the formal regular expression $($a$|$b$)*.$

let fresh $=$

$$ let cntr $=$ ref $0$ in

$$ fun $()->$

$$ cntr :$=!$cntr $+1$ ;

$!$cntr;;

string$\_$to$\_$nfa s

Type: string $->$ nfa

Description: This function takes a string for a regular expression, parses the string, converts it into a regexp, and transforms it to an nfa, using your regexp$\_$to$\_$nfa function. As such, for this function to work, your regexp$\_$to$\_$nfa function must be working. In the starter files, we have provided the function string$\_$to$\_$regexp that parses strings into regexp values, described next.

string$\_$to$\_$regexp s

Type: string $->$ regexp

Description: This function takes a string for a regular expression, parses the string, and outputs its equivalent regexp. If the parser determines that the regular expression has illegal syntax, it will raise an IllegalExpression exception.

Examples:

string$\_$to$\_$regexp $"$a$"=$ Char $\text{'}$a$\text{'}$

string$\_$to$\_$regexp $"($a$|$b$)"=$ Union $($Char $\text{'}$a$\text{'},$ Char $\text{'}$b$\text{'})$

string$\_$to$\_$regexp $"$ab$"=$ Concat$($Char $\text{'}$a$\text{'},$ Char $\text{'}$b$\text{'})$

string$\_$to$\_$regexp "aab" $=$ Concat$($Char $\text{'}$a$\text{'},$Concat$($Char $\text{'}$a$\text{'},$ Char $\text{'}$b$\text{'}))$

string$\_$to$\_$regexp $"($a$|$E$)*"=$ Star$($Union$($Char $\text{'}$a$\text{'},$Empty$\_$String$))$

string$\_$to$\_$regexp $"($a$|$E$)*($a$|$b$)"=$ Concat$($Star$($Union$($Char $\text{'}$a$\text{'},$Empty$\_$String$)),$Union$($Char $\text{'}$a$\text{'},$Char $\text{'}$b$\text{'}))$

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;;

let explode $($s: string$)$ : char list $=$

$$ let rec exp i l $=$

$$ if i $<0$ then l else exp $($i $-1)($s$.[$i$]$ :: l$)$

$$ in

$$ exp $($String$.$length s $-1)[]$;;

let rec elem x a $=$

$$ match a with

$|$ h::t $->($h $=$ x$)||($elem x t$)$

$|[]->$ false;;

let rec insert x a $=$

$$ if not $($elem x a$)$ then x::a else a;;

let insert$\_$all xs a $=$

$$ List.fold$\_$right insert xs a;;

let rec subset a b $=$

$$ match a with

$|$ h::t $->($elem h b$)$ && $($subset t b$)$

$|[]->$ true;;

let rec eq a b $=($subset a b$)$ && $($subset b a$)$;;

let rec remove x a $=$

$$ match a with

$|$ h::t $->$ if h $=$ x then t else h::$($remove x t$)$

$|[]->[]$;;

let rec diff a b $=$

$$ match b with

$|[]->$ a

$|$ h::t $->$ diff $($remove h a$)$ t;;

$(*$ Wrapper for old P$3*)$

let rec minus a b $=$ diff a b;;

let rec union a b $=$

$$ match a with

$|$ h::t $->$ insert h $($union t b$)$

$|[]->$

$($match b with

$|$ h::t $->$ insert h $($union $[]$ t$)$

$|[]->[])$;;

let rec intersection a b $=$

$$ match a with

$|$ h::t $->$ if elem h b then insert h $($intersection t b$)$ else $($intersection t b$)$

$|[]->[]$;;

let rec product a b $=$

$$ let rec product$\_$help x b $=$

$$ match b with

$|$ h::t $->$ insert $($x$,$ h$)($product$\_$help x t$)$

$|[]->[]$ in

$$ match a with

$|$ h::t $->$ union $($product$\_$help h b$)($product t b$)$

$|[]->[]$;;

let rec cat x a $=$

$$ match a with

$|[]->[]$

$|$ h::t $->($x$,$h$)$::$($cat x t$)$;;