CONSIDERIn Ocaml:type ('q, 's) transi = 'q * 's option * 'q type ('q, 's) nfa_y = { sigma : 's list; qs : 'q list; q0 : '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)] } mo n 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] PROBLEM: Complete function acce n t, of Type ('q, char) nfa_y -> string -> bool which takes an NFA nfa and a string s, and returns true if the NFA accepts the string. Example: 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)]};; acce dfa "" = false;; (* dfa_ex is the NFA defined above *)acce dfa "zx" = true;;acce dfa "zyx" = false;;acce dfa "zyzx" = true;;

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

100%

CONSIDER
In Ocaml:
type ('q, 's) transi = 'q * 's option * 'q

type ('q, 's) nfa_y = { sigma : 's list; qs : 'q list; q0 : '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)] }

mo n 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]

PROBLEM: Complete function

acce n t, of Type ('q, char) nfa_y -> string -> bool

which takes an NFA nfa and a string s, and returns true if the NFA accepts the string.

Example:

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

acce dfa "" = false;; (* dfa_ex is the NFA defined above *)
acce dfa "zx" = true;;
acce dfa "zyx" = false;;
acce dfa "zyzx" = true;;

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.

Similar questions