1. What does NP stands for in complexity classes theory?
a) Non polynomial
b) Non-deterministic polynomial
c) Both (a) and (b)
d) None of the mentioned
View Answer
Answer: b
Explanation: NP is said to be one of the most fundamental complexity classes. NP is an acronym for Non deterministic polynomial time.
Explanation: NP is said to be one of the most fundamental complexity classes. NP is an acronym for Non deterministic polynomial time.
2. A ___________ is a multi tape turing machine whose input tape is read only.
a) Counter Machine
b) Multi-stack
c) Alternating Turing machine
d) None of the mentioned
View Answer
Answer: a
Explanation: Counter machines are offline(a multitape turing machine whose input is read only) whose storage tapes are semi-infinite and whose tape symbols contains only two symbols Z and a blank symbol B.
Explanation: Counter machines are offline(a multitape turing machine whose input is read only) whose storage tapes are semi-infinite and whose tape symbols contains only two symbols Z and a blank symbol B.
3. Which of the following can generate Unrestricted grammars?
a) Pentonnen Normal form
b) Floyd Normal form
c) Greibach Normal form
d) None of the mentioned
View Answer
Answer: a
Explanation: Pentonnen Normal form(for Unrestricted grammars) is a special case where there is a slight modification in the format of Kuroda Normal form.
AB->AD
A->BC
A->a
Explanation: Pentonnen Normal form(for Unrestricted grammars) is a special case where there is a slight modification in the format of Kuroda Normal form.
AB->AD
A->BC
A->a
a) tape alphabets
b) number of tapes
c) number of states
d) none of these
View Answer
Answer: d
Explanation: Another procedure to restrict a turing machine is to limit the size of tape alphabet or reduce the number of states. If the tape alphabets, number of tapes or number of states are limited, then there is only a finite number of different turing machine, so the restricted model is more powerful than the original one.
Explanation: Another procedure to restrict a turing machine is to limit the size of tape alphabet or reduce the number of states. If the tape alphabets, number of tapes or number of states are limited, then there is only a finite number of different turing machine, so the restricted model is more powerful than the original one.
a) Subset Construction Method
b) Power Set Construction Method
c) Thompson Construction Method
d) Scott Construction Method
View Answer
Answer: c
Explanation: Thompson Construction method is used to turn a regular expression in an NFA by fragmenting the given regular expression through the operations performed on the input alphabets.
Explanation: Thompson Construction method is used to turn a regular expression in an NFA by fragmenting the given regular expression through the operations performed on the input alphabets.
a) Quick Sort
b) Bucket Sort
c) Radix Sort
d) Merge Sort
View Answer
Answer: a
Explanation: Quicksort is the method of choice in many applications( Unix sort command) with O(nlogn) in worst case.
Explanation: Quicksort is the method of choice in many applications( Unix sort command) with O(nlogn) in worst case.
a) travelling salesman problem
b) halting problem
c) hitting set
d) none of the mentioned
View Answer
Answer: a
Explanation: Hamilton circuit problem is a special case of travelling salesman problem, obtained by setting the distance between two cities to one if they are adjacent and two otherwise, and verifying that the total distance travelled is equal to n (if so, the route is a Hamiltonian circuit; if there is no Hamiltonian circuit then the shortest route will be longer).
Explanation: Hamilton circuit problem is a special case of travelling salesman problem, obtained by setting the distance between two cities to one if they are adjacent and two otherwise, and verifying that the total distance travelled is equal to n (if so, the route is a Hamiltonian circuit; if there is no Hamiltonian circuit then the shortest route will be longer).
a) Context free
b) Not context free
c) Regular
d) None of the mentioned
View Answer
Answer: b
Explanation: The pumping lemma is often used to prove that a given language L is non-context-free, by showing that arbitrarily long strings s are in L that cannot be “pumped” without producing strings outside L.
Explanation: The pumping lemma is often used to prove that a given language L is non-context-free, by showing that arbitrarily long strings s are in L that cannot be “pumped” without producing strings outside L.
a) Minecraft
b) Minesweeper
c) Dwarf Fortress
d) All of the mentioned
View Answer
Answer: d
Explanation: Many games fall under the category og turing complete:
a) Minecraft
b) Minesweeper
c) Dwarf Fortress
d) Conway’s Game of Life
e) Pokemon Yellow, etc.
Explanation: Many games fall under the category og turing complete:
a) Minecraft
b) Minesweeper
c) Dwarf Fortress
d) Conway’s Game of Life
e) Pokemon Yellow, etc.
a) It is recursively ennumerable
b) It is undecidable
c) Both (a) and (b)
d) None of the mentioned
View Answer
Answer: c
Explanation: Halting problem: Does a given Turing machine M halt on a given input w?
Explanation: Halting problem: Does a given Turing machine M halt on a given input w?
a) a total turing machine exists
b) a turing machine that halts for every input
c) turing machine rejects if the input does not belong to the language
d) all of the mentioned
View Answer
Answer: d
Explanation: A formal language is called recursive if it is a recursive subset of the set of all possible finite sequences over the alphabet of the language.
Explanation: A formal language is called recursive if it is a recursive subset of the set of all possible finite sequences over the alphabet of the language.
a) A->BC
b) A->a
c) S->e
d) All of the mentioned
View Answer
Answer: d
Explanation: in CNF, the production rules are of the form:
A->BC
A-> a
S->e
Explanation: in CNF, the production rules are of the form:
A->BC
A-> a
S->e
S->aA
A->a
A->B
B-> A
B->bb
Which of the following is the production of B after simplification by removal of unit productions?
a) A
b) bb
c) aA
d) A| bb
View Answer
Answer: b
Explanation: The simplified grammar can be presented as follows:
S->aA| aB
A->a
B-> bb
Explanation: The simplified grammar can be presented as follows:
S->aA| aB
A->a
B-> bb
A-> x1x2x3…xn
put into P’ that production as well as all those generated by replacing null variables with e in all possible combinations. If all x(i) are nullable,
a) A->e is put into P’
b) A->e is not put into P’
c) e is a member of G’
d) None of the mentioned
View Answer
Answer: b
Explanation: It is an exception that A->e is not put into P’ if all x(i) are nullable variables.
Explanation: It is an exception that A->e is not put into P’ if all x(i) are nullable variables.
A-> a| aaA| abBc
B-> abba| b
a) A-> a| aaA| ababbAc| abbc
b) A-> a| aaA| ababbAc| abbc, B-> abba|b
c) A-> a| aaA| abbc, B->abba
d) None of the mentioned
View Answer
Answer: a
Explanation: Using the substitution rules, we can simply eradicate what is useless and thus produce the simplified result i.e. A-> a| aaA| ababbAc| abbc.
Explanation: Using the substitution rules, we can simply eradicate what is useless and thus produce the simplified result i.e. A-> a| aaA| ababbAc| abbc.
