1. A randomized algorithm uses random bits as input inorder to achieve a _____________ good performance over all possible choice of random bits.
a) worst case
b) best case
c) average case
d) none of the mentioned
View Answer
Answer: c
Explanation: A randomized algorithm is an algorithm that employs a degree of randomness as a part of its logic using random bits as inputs and in hope of producing average case good performace.
Explanation: A randomized algorithm is an algorithm that employs a degree of randomness as a part of its logic using random bits as inputs and in hope of producing average case good performace.
a) Regular language
b) Context free language
c) Context Sensitive Language
d) None of the mentioned
View Answer
Answer: c
Explanation: Membership of a string in a language defined by an arbitrary context sensitive grammar, or by an arbitrary determinisic context sensitive grammar, is a PSPACE -complete problem.
Explanation: Membership of a string in a language defined by an arbitrary context sensitive grammar, or by an arbitrary determinisic context sensitive grammar, is a PSPACE -complete problem.
a) Linear Programming
b) Greatest common divisor
c) Maximum matching
d) None of the mentioned
View Answer
Answer: d
Explanation: In graph theory, a matching or independent edge set in a graph G is a set of edges without common vertices. Given a graph (V, E), a matching M in G is a set of pairwise non adjacent edges i.e. no two edges share a common vertex.
Explanation: In graph theory, a matching or independent edge set in a graph G is a set of edges without common vertices. Given a graph (V, E), a matching M in G is a set of pairwise non adjacent edges i.e. no two edges share a common vertex.
Fill in the blank:
Rec-DFA is ___________
a) Undecidable
b) Decidable
c) Non finite
d) None of the mentioned
View Answer
Answer: b
Explanation: Under decidablity of regular language properties we have the following lemma which states that A DFA which recognizes an input w is decidable.
Explanation: Under decidablity of regular language properties we have the following lemma which states that A DFA which recognizes an input w is decidable.
a) Subroutines
b) Multiple tracks
c) Shifting over
d) Recursion
View Answer
Answer: d
Explanation: Except Recursion, all the other options are techniques of Turing Machine construction which further includes, Checking off symbols and Storage in finite control.
Explanation: Except Recursion, all the other options are techniques of Turing Machine construction which further includes, Checking off symbols and Storage in finite control.
a) one
b) two
c) n
d) infinite
View Answer
Answer: a
Explanation: In a n-track Turing machine, one head reads and writes on all tracks simultaneously. A tape position in a n-track Turing Machine contains n symbols from the tape alphabet.
Explanation: In a n-track Turing machine, one head reads and writes on all tracks simultaneously. A tape position in a n-track Turing Machine contains n symbols from the tape alphabet.
a) Abstract machine
b) Any quantum algorithm can be expressed formally as a particular quantum turing machine
c) Gives a solution to ‘Is a universal quantum computer sufficient’
d) None of the mentioned
View Answer
Answer: c
Explanation: ‘Is a universal quantum computer sufficient’ is one of the unsolved problem from physics.
Explanation: ‘Is a universal quantum computer sufficient’ is one of the unsolved problem from physics.
8. State true or false:
Statement: Two track turing machine is equivalent to a standard turing machine.
a) true
b) false
View Answer
Answer: a
Explanation: This can be generalized for n- tracks and can be proved equivalent using ennumerable languages.
Explanation: This can be generalized for n- tracks and can be proved equivalent using ennumerable languages.
a) Random access storage program
b) Random access stored program
c) Randomly accessed stored program
d) Random access storage programming
View Answer
Answer: b
Explanation: RASP or Random access stored program is an abstract machine that has instances like modern stored computers.
Explanation: RASP or Random access stored program is an abstract machine that has instances like modern stored computers.
10. A Language L may not be accepted by a Turing Machine if:
a) It it is recursively ennumerable
b) It is recursive
c) L can be ennumerated by some turing machine
d) None of the mentioned
View Answer
Answer: b
Explanation: A language L is recursively ennumerable if and only if it can be ennumerated by some turing machine. A recursive ennumerable language may or may not be recursive.
Explanation: A language L is recursively ennumerable if and only if it can be ennumerated by some turing machine. A recursive ennumerable language may or may not be recursive.
11. A turing machine is a
a) real machine
b) abstract machine
c) hypothetical machine
d) more than one option is correct
View Answer
Answer: d
Explanation: A turing machine is abstract or hypothetical machine thought by mathematician Alan Turing in 1936 capable of simulating any algorithm, however complicated it is.
Explanation: A turing machine is abstract or hypothetical machine thought by mathematician Alan Turing in 1936 capable of simulating any algorithm, however complicated it is.
a) finite memory tape
b) infinite memory tape
c) depends on the algorithm
d) none of the mentioned
View Answer
Answer: b
Explanation: The turing machine operates on an infinite memory tape divided into cells. The machine positions its head over the cell and reads the symbol.
Explanation: The turing machine operates on an infinite memory tape divided into cells. The machine positions its head over the cell and reads the symbol.
a) input tape
b) head
c) state register
d) none of the mentioned
View Answer
Answer: d
Explanation: A state register is one which stores the state of the turing machine, one of the finitely many. Among these is the special start state with which the state register is initialized.
Explanation: A state register is one which stores the state of the turing machine, one of the finitely many. Among these is the special start state with which the state register is initialized.
a) {w: nA=nB=nC}
b) {a*b*c*}
c) {a100b100}
d) All of the mentioned
View Answer
Answer: d
Explanation: {a*b*c*} and (c) are regular languages while option (a) is not context free language.
Explanation: {a*b*c*} and (c) are regular languages while option (a) is not context free language.
a) Backus Naur Form
b) Kuroda Normal Form
c) Greibach Normal Form
d) Chomsky Normal Form
View Answer
Answer: a
Explanation: Donald Knuth implied a BNF” syntax in which all definitions have such a form may be said to be in ”Floyd Normal Form”.
A->B|C
A->BC
A->a
Explanation: Donald Knuth implied a BNF” syntax in which all definitions have such a form may be said to be in ”Floyd Normal Form”.
A->B|C
A->BC
A->a
