In Ocaml, iven the types: 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; } And the example inputs: let nfa2 = { sigma = ['z']; qs = [1; 2; 3]; q0 = 1; fs = [3]; delta = [(1, Some 'z', 2); (2, None, 3)] };; let dfa2 = { sigma = ['z'; 'y'; 'x']; qs = [1; 2; 3]; q0 = 1; fs = [3]; delta = [(1, Some 'z', 2); (2, Some 'y', 3); (3, Some 'x', 1)] };; implement the following functions: let stateFresh (nfa: ('p,'t) nfa_t) (qt: 'p list) : 'p list list = failwith "unimplemented" (*Takes an NFA and a list of states, 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. Examples: stateFresh nfa2 [1] = [[2; 3]] stateFresh dfa2 [1; 2] = [[2]; [1]; [3]]stateFresh dfa2 [2; 3] = [[]; [1]; [3]]*) let freshTrans (nfa: ('p,'t) nfa_t) (qt: 'p list) : ('p list, 't) transition list = failwith "unimplemented" (* The inputs are an NFA and a list of states. The output is a transition list. 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. Examples: freshTrans nfa2 [1] = [([1], Some 'z', [2; 3])]freshTrans dfa2 [1; 2] = [([1; 2], Some 'z', [2]); ([1; 2], Some 'y', [1]); ([1; 2], Some 'x', [3])]freshTrans dfa2 [2; 3] = [([2; 3], Some 'z', []); ([2; 3], Some 'y', [1]); ([2; 3], Some 'x', [3])]*) let freshFin (nfa: ('p,'t) nfa_t) (qt: 'q list) : 'p list list = failwith "unimplemented" (*Takes an NFA and a list of states, return [qt] if an element of qt is a final state in the provided NFA. Returns an empty list otherwise. Examples: freshFin dfa2 [1;2; 3] = [[1; 2; 3]]freshFin dfa2 [1; 2] = []*)

In Ocaml, iven the types: 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; } And the example inputs: let nfa2 = { sigma = ['z']; qs = [1; 2; 3]; q0 = 1; fs = [3]; delta = [(1, Some 'z', 2); (2, None, 3)] };; let dfa2 = { sigma = ['z'; 'y'; 'x']; qs = [1; 2; 3]; q0 = 1; fs = [3]; delta = [(1, Some 'z', 2); (2, Some 'y', 3); (3, Some 'x', 1)] };; implement the following functions: let stateFresh (nfa: ('p,'t) nfa_t) (qt: 'p list) : 'p list list = failwith "unimplemented" (Takes an NFA and a list of states, 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. Examples: stateFresh nfa2 [1] = [[2; 3]] stateFresh dfa2 [1; 2] = [[2]; [1]; [3]]stateFresh dfa2 [2; 3] = [[]; [1]; [3]]) let freshTrans (nfa: ('p,'t) nfa_t) (qt: 'p list) : ('p list, 't) transition list = failwith "unimplemented" (* The inputs are an NFA and a list of states. The output is a transition list. 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. Examples: freshTrans nfa2 [1] = [([1], Some 'z', [2; 3])]freshTrans dfa2 [1; 2] = [([1; 2], Some 'z', [2]); ([1; 2], Some 'y', [1]); ([1; 2], Some 'x', [3])]freshTrans dfa2 [2; 3] = [([2; 3], Some 'z', []); ([2; 3], Some 'y', [1]); ([2; 3], Some 'x', [3])]) let freshFin (nfa: ('p,'t) nfa_t) (qt: 'q list) : 'p list list = failwith "unimplemented" (Takes an NFA and a list of states, return [qt] if an element of qt is a final state in the provided NFA. Returns an empty list otherwise. Examples: freshFin dfa2 [1;2; 3] = [[1; 2; 3]]freshFin dfa2 [1; 2] = []*)

Database System Concepts

7th Edition

ISBN:9780078022159

Author:Abraham Silberschatz Professor, Henry F. Korth, S. Sudarshan

Publisher:Abraham Silberschatz Professor, Henry F. Korth, S. Sudarshan

Chapter1: Introduction

Section: Chapter Questions

Problem 1PE

See similar textbooks

Related questions

Concept explainers

Question

In Ocaml, iven the types:

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

And the example inputs:

let nfa2 = { sigma = ['z']; qs = [1; 2; 3]; q0 = 1; fs = [3]; delta = [(1, Some 'z', 2); (2, None, 3)] };;

let dfa2 = { sigma = ['z'; 'y'; 'x']; qs = [1; 2; 3]; q0 = 1; fs = [3]; delta = [(1, Some 'z', 2); (2, Some 'y', 3); (3, Some 'x', 1)] };;

implement the following functions:

let stateFresh (nfa: ('p,'t) nfa_t) (qt: 'p list) : 'p list list = failwith "unimplemented"

(*Takes an NFA and a list of states, 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.

Examples:

stateFresh nfa2 [1] = [[2; 3]]
stateFresh dfa2 [1; 2] = [[2]; [1]; [3]]
stateFresh dfa2 [2; 3] = [[]; [1]; [3]]*)

let freshTrans (nfa: ('p,'t) nfa_t) (qt: 'p list) : ('p list, 't) transition list = failwith "unimplemented"

(* The inputs are an NFA and a list of states. The output is a transition list. 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.

Examples:

freshTrans nfa2 [1] = [([1], Some 'z', [2; 3])]
freshTrans dfa2 [1; 2] = [([1; 2], Some 'z', [2]); ([1; 2], Some 'y', [1]); ([1; 2], Some 'x', [3])]
freshTrans dfa2 [2; 3] = [([2; 3], Some 'z', []); ([2; 3], Some 'y', [1]); ([2; 3], Some 'x', [3])]*)

let freshFin (nfa: ('p,'t) nfa_t) (qt: 'q list) : 'p list list = failwith "unimplemented"

(*Takes an NFA and a list of states, return [qt] if an element of qt is a final state in the provided NFA. Returns an empty list otherwise.

Examples:

freshFin dfa2 [1;2; 3] = [[1; 2; 3]]
freshFin dfa2 [1; 2] = []*)

Expert Solution

Step by step

Solved in 2 steps

SEE SOLUTION Check out a sample Q&A here

Knowledge Booster

Learn more about

Need a deep-dive on the concept behind this application? Look no further. Learn more about this topic, computer-science and related others by exploring similar questions and additional content below.