Consider the following types and functions type ('q, 's) transition = 'q * 's option * 'q type ('q, 's) nfa_t = { sigma : 's list; qs : 'q list; q0 : 'q; fs : 'q list; delta : ('q, 's) transition list; } mo n ql t, of Type: ('q, 's) nfa_t -> '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. e_clo n ql, of Type: ('q, 's) nfa_t -> '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. Complete function acce n t, of Type ('q, char) nfa_t -> string -> bool which takes an NFA nfa and a string s, and returns true if the NFA accepts the string.
Consider the following types and functions
type ('q, 's) transition = 'q * 's option * 'q
type ('q, 's) nfa_t = { sigma : 's list; qs : 'q list; q0 : 'q; fs : 'q list; delta : ('q, 's) transition list; }
mo n ql t, of Type: ('q, 's) nfa_t -> '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.
e_clo n ql, of Type: ('q, 's) nfa_t -> '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.
Complete function
acce n t, of Type ('q, char) nfa_t -> string -> bool
which takes an NFA nfa and a string s, and returns true if the NFA accepts the string.
Step by step
Solved in 2 steps
