In Ocaml: transFresh nfa qs Type: ('q, 's) nfa_t -> 'q list -> ('q list, 's) transition listNO IMPERATIVES.THIS INCLUDES REFERENCES, FOR AND WHILE LOOPS, AND HASHMAPS Description: 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. This may seem a little confusing at first, so make sure you look at the examples below! Examples: 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; } let nfa_ex = { sigma = ['a']; qs = [0; 1; 2]; q0 = 0; fs = [2]; delta = [(0, Some 'a', 1); (1, None, 2)] } let dfa_ex = { sigma = ['a'; 'b'; 'c']; qs = [0; 1; 2]; q0 = 0; fs = [2]; delta = [(0, Some 'a', 1); (1, Some 'b', 0); (1, Some 'c', 2)] } transFresh nfa_ex [0] = [([0], Some 'a', [1; 2])] transFresh dfa_ex [0; 1] = [([0; 1], Some 'a', [1]); ([0; 1], Some 'b', [0]); ([0; 1], Some 'c', [2])] transFresh dfa_ex [1; 2] = [([1; 2], Some 'a', []); ([1; 2], Some 'b', [0]); ([1; 2], Some 'c', [2])] Explanation: Starting from state 0 in nfa_ex, we can move only to state 1 on 'a' and then from state 1 to state 2 on epsilon, which gives us the tuple ([0], Some 'a', [1; 2]). 'a' is the only character in the alphabet. So, we return [([0], Some 'a', [1; 2])]. Starting from either state 0 or state 1 in dfa_ex, we want to see where we can move to. If we start at 0, we can move to 1 on 'a', and if we start at 1, there isn't an 'a' transition. There are no states we can move to from 1 via epsilons (because it's a DFA), so we have the tuple ([0; 1], Some 'a', [1]). Then, starting again from either state 0 or state 1, we can move to 0 on 'b' from 1, and there isn't a 'b' transition from 0 to another state. There are no states we can move to from 0 via epsilons, so we have the tuple ([0; 1], Some 'b', [0]). Then, starting again from either state 0 or state 1, we can move to 2 on 'c' from 1, and there isn't a 'c' transition from 0 to another state. There are no states we can move to from 2 via epsilons, so we have the tuple ([0; 1], Some 'c', [2]). So, our overall returned list is [([0; 1], Some 'a', [1]); ([0; 1], Some 'b', [0]); ([0; 1], Some 'c', [2])]. Starting from either state 1 or state 2 in dfa_ex, there is no 'a' transition that starts from either state 1 or state 2. So, we have ([1;2], Some 'a', []). Then, starting again from either state 1 or state 2, we can move to 0 on 'b' from 1, and there isn't a 'b' transition from 2 to another state. There are no states we can move to from 0 via epsilons (because it's a DFA), so we have ([1;2], Some 'b', [0]). Then, starting again from either state 1 or state 2, we can move to state 2 on 'c' from 1, and there isn't a 'c' transition from 2 to another state. There are no states we can move to from 2 via epsilons, so we have ([1;2], Some 'c', [2]). So, our overall returned list is [([1;2], Some 'a', []); ([1;2], Some 'b', [0]); ([1;2], Some 'c', [2])].
In Ocaml: transFresh nfa qs Type: ('q, 's) nfa_t -> 'q list -> ('q list, 's) transition listNO IMPERATIVES.THIS INCLUDES REFERENCES, FOR AND WHILE LOOPS, AND HASHMAPS Description: 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. This may seem a little confusing at first, so make sure you look at the examples below! Examples: 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; } let nfa_ex = { sigma = ['a']; qs = [0; 1; 2]; q0 = 0; fs = [2]; delta = [(0, Some 'a', 1); (1, None, 2)] } let dfa_ex = { sigma = ['a'; 'b'; 'c']; qs = [0; 1; 2]; q0 = 0; fs = [2]; delta = [(0, Some 'a', 1); (1, Some 'b', 0); (1, Some 'c', 2)] } transFresh nfa_ex [0] = [([0], Some 'a', [1; 2])] transFresh dfa_ex [0; 1] = [([0; 1], Some 'a', [1]); ([0; 1], Some 'b', [0]); ([0; 1], Some 'c', [2])] transFresh dfa_ex [1; 2] = [([1; 2], Some 'a', []); ([1; 2], Some 'b', [0]); ([1; 2], Some 'c', [2])] Explanation: Starting from state 0 in nfa_ex, we can move only to state 1 on 'a' and then from state 1 to state 2 on epsilon, which gives us the tuple ([0], Some 'a', [1; 2]). 'a' is the only character in the alphabet. So, we return [([0], Some 'a', [1; 2])]. Starting from either state 0 or state 1 in dfa_ex, we want to see where we can move to. If we start at 0, we can move to 1 on 'a', and if we start at 1, there isn't an 'a' transition. There are no states we can move to from 1 via epsilons (because it's a DFA), so we have the tuple ([0; 1], Some 'a', [1]). Then, starting again from either state 0 or state 1, we can move to 0 on 'b' from 1, and there isn't a 'b' transition from 0 to another state. There are no states we can move to from 0 via epsilons, so we have the tuple ([0; 1], Some 'b', [0]). Then, starting again from either state 0 or state 1, we can move to 2 on 'c' from 1, and there isn't a 'c' transition from 0 to another state. There are no states we can move to from 2 via epsilons, so we have the tuple ([0; 1], Some 'c', [2]). So, our overall returned list is [([0; 1], Some 'a', [1]); ([0; 1], Some 'b', [0]); ([0; 1], Some 'c', [2])]. Starting from either state 1 or state 2 in dfa_ex, there is no 'a' transition that starts from either state 1 or state 2. So, we have ([1;2], Some 'a', []). Then, starting again from either state 1 or state 2, we can move to 0 on 'b' from 1, and there isn't a 'b' transition from 2 to another state. There are no states we can move to from 0 via epsilons (because it's a DFA), so we have ([1;2], Some 'b', [0]). Then, starting again from either state 1 or state 2, we can move to state 2 on 'c' from 1, and there isn't a 'c' transition from 2 to another state. There are no states we can move to from 2 via epsilons, so we have ([1;2], Some 'c', [2]). So, our overall returned list is [([1;2], Some 'a', []); ([1;2], Some 'b', [0]); ([1;2], Some 'c', [2])].
C++ Programming: From Problem Analysis to Program Design
8th Edition
ISBN:9781337102087
Author:D. S. Malik
Publisher:D. S. Malik
Chapter13: Overloading And Templates
Section: Chapter Questions
Problem 15PE
Related questions
Concept explainers
Types of Linked List
A sequence of data elements connected through links is called a linked list (LL). The elements of a linked list are nodes containing data and a reference to the next node in the list. In a linked list, the elements are stored in a non-contiguous manner and the linear order in maintained by means of a pointer associated with each node in the list which is used to point to the subsequent node in the list.
Linked List
When a set of items is organized sequentially, it is termed as list. Linked list is a list whose order is given by links from one item to the next. It contains a link to the structure containing the next item so we can say that it is a completely different way to represent a list. In linked list, each structure of the list is known as node and it consists of two fields (one for containing the item and other one is for containing the next item address).
Question
In Ocaml:
transFresh nfa qs
Type: ('q, 's) nfa_t -> 'q list -> ('q list, 's) transition list
NO IMPERATIVES.
THIS INCLUDES REFERENCES, FOR AND WHILE LOOPS, AND HASHMAPS
NO IMPERATIVES.
THIS INCLUDES REFERENCES, FOR AND WHILE LOOPS, AND HASHMAPS
Description: 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. This may seem a little confusing at first, so make sure you look at the examples below!
Examples:
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; }
let nfa_ex = {
sigma = ['a'];
qs = [0; 1; 2];
q0 = 0;
fs = [2];
delta = [(0, Some 'a', 1); (1, None, 2)]
}
let dfa_ex = {
sigma = ['a'; 'b'; 'c'];
qs = [0; 1; 2];
q0 = 0;
fs = [2];
delta = [(0, Some 'a', 1); (1, Some 'b', 0); (1, Some 'c', 2)]
}
transFresh nfa_ex [0] = [([0], Some 'a', [1; 2])]
transFresh dfa_ex [0; 1] = [([0; 1], Some 'a', [1]); ([0; 1], Some 'b', [0]); ([0; 1], Some 'c', [2])]
transFresh dfa_ex [1; 2] = [([1; 2], Some 'a', []); ([1; 2], Some 'b', [0]); ([1; 2], Some 'c', [2])]
Explanation:
Starting from state 0 in nfa_ex, we can move only to state 1 on 'a' and then from state 1 to state 2 on epsilon, which gives us the tuple ([0], Some 'a', [1; 2]). 'a' is the only character in the alphabet. So, we return [([0], Some 'a', [1; 2])].
Starting from either state 0 or state 1 in dfa_ex, we want to see where we can move to. If we start at 0, we can move to 1 on 'a', and if we start at 1, there isn't an 'a' transition. There are no states we can move to from 1 via epsilons (because it's a DFA), so we have the tuple ([0; 1], Some 'a', [1]). Then, starting again from either state 0 or state 1, we can move to 0 on 'b' from 1, and there isn't a 'b' transition from 0 to another state. There are no states we can move to from 0 via epsilons, so we have the tuple ([0; 1], Some 'b', [0]). Then, starting again from either state 0 or state 1, we can move to 2 on 'c' from 1, and there isn't a 'c' transition from 0 to another state. There are no states we can move to from 2 via epsilons, so we have the tuple ([0; 1], Some 'c', [2]). So, our overall returned list is [([0; 1], Some 'a', [1]); ([0; 1], Some 'b', [0]); ([0; 1], Some 'c', [2])].
Starting from either state 1 or state 2 in dfa_ex, there is no 'a' transition that starts from either state 1 or state 2. So, we have ([1;2], Some 'a', []). Then, starting again from either state 1 or state 2, we can move to 0 on 'b' from 1, and there isn't a 'b' transition from 2 to another state. There are no states we can move to from 0 via epsilons (because it's a DFA), so we have ([1;2], Some 'b', [0]). Then, starting again from either state 1 or state 2, we can move to state 2 on 'c' from 1, and there isn't a 'c' transition from 2 to another state. There are no states we can move to from 2 via epsilons, so we have ([1;2], Some 'c', [2]). So, our overall returned list is [([1;2], Some 'a', []); ([1;2], Some 'b', [0]); ([1;2], Some 'c', [2])].
Expert Solution
This question has been solved!
Explore an expertly crafted, step-by-step solution for a thorough understanding of key concepts.
Step by step
Solved in 2 steps
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.Recommended textbooks for you
C++ Programming: From Problem Analysis to Program…
Computer Science
ISBN:
9781337102087
Author:
D. S. Malik
Publisher:
Cengage Learning
C++ Programming: From Problem Analysis to Program…
Computer Science
ISBN:
9781337102087
Author:
D. S. Malik
Publisher:
Cengage Learning