Multiple choice question for engineering
Set 1
1. A turing machine with several tapes in known as:
a) Multi-tape turing machine
b) Poly-tape turing maching
c) Universal turing machine
d) All of the mentioned
Answer
Answer: a [Reason:] A multitape turing machine is an ordinary turing machine with multiple tapes. Each tape has its own head to control the read and write.
2. A multitape turing machine is ________ powerful than a single tape turing machine.
a) more
b) less
c) equal
d) none of the mentioned
Answer
Answer: a [Reason:] The multitape turing machine model seems much powerful than the single tape model, but any multi tape machine, no matter how many tapes, can be simulated by single taped TM.
3. In what ratio, more computation time is needed to simulate multitape turing machines using single tape turing machines?
a) doubly
b) triple
c) quadratically
d) none of the mentioned
Answer
Answer: c [Reason:] Thus, multitape turing machines cannot calculate any more functions than single tape machines.
4. Which of the following is true for two stack turing machines?
a) one read only input
b) two storage tapes
c) Both (a) and (b)
d) None of the mentioned
Answer
Answer: c [Reason:] Two-stack Turing machines have a read-only input and two storage tapes. If a head moves left on either tape a blank is printed on that tape, but one symbol from a “library” can be printed.
5. Which of the following is not a Non deterministic turing machine?
a) Alternating Turing machine
b) Probabalistic Turing machine
c) Read-only turing machine
d) None of the mentioned
Answer
Answer: c [Reason:] A read only turing machine or 2 way deterministic finite automaton is a class of model of computability that behaves like a turing machine, and can move in both directions across input, except cannot write to its input tape.
6. Which of the turing machines have existential and universal states?
a) Alternating Turing machine
b) Probalistic Turing machine
c) Read-only turing machine
d) None of the mentioned
Answer
Answer: a [Reason:] ATM is divide into two sets: an existential state is accepting if some transitions leads to an accepting state; an universal state is accepting if every transition leads to an accepting state.
7. Which of the following is false for Quantum Turing machine?
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
Answer
Answer: c [Reason:] ‘Is a universal quantum computer sufficient’ is one of the unsolved problem from physics.
8. A deterministic turing machine is:
a) ambiguous turing machine
b) unambiguous turing machine
c) non-deterministic
d) none of the mentioned
Answer
Answer: b [Reason:] A deterministic turing machine is unambiguous and for every input, there is exactly one operation possible. It is a subset of non-deterministic Turing machines.
9. Which of the following is true about Turing’s a-machine?
a) a stands for automatic
b) left ended, right end-infinite
c) finite number of tape symbols were allowed
d) all of the mentioned
Answer
Answer: d [Reason:] Turings a- machine or automatic machine was left ended,right end infinite.Any of finite number of tape symbols were allowed and the 5 tuples were not in order.
10. Which of the following is a multi tape turing machine?
a) Post turing Machine
b) Wang-B Machine
c) Oblivious turing Machine
d) All of the mentioned
Answer
Answer: c [Reason:] An oblivious turing machine where movements of various heads are fixed functions of time, independent of the input. Pippenger and Fischer showed that any computation that can be performed by a multi-tape Turing machine in n steps can be performed by an oblivious two-tape Turing machine in O(n log n) steps.
Set 2
1. Which of the following options is correct?
Statement 1: Initial State of NFA is Initial State of DFA.
Statement 2: The final state of DFA will be every combination of final state of NFA.
a) Statement 1 is true and Statement 2 is true
b) Statement 1 is true and Statement 2 is false
c) Statement 1 can be true and Statement 2 is true
d) Statement 1 is false and Statement 2 is also false
Answer
Answer: a [Reason:] Statement 1 and 2 always true for a given Language.
2. Given Language: L= {ab U aba}*
If X is the minimum number of states for a DFA and Y is the number of states to construct the NFA,
|X-Y|=?
a) 2
b) 3
c) 4
d) 1
Answer
Answer: a [Reason:] Construct the DFA and NFA individually, and the attain the difference of states.
3. An automaton that presents output based on previous state or current input:
a) Acceptor
b) Classifier
c) Transducer
d) None of the mentioned.
Answer
Answer: c [Reason:] A transducer is an automaton that produces an output on the basis of what input has been given currently or previous state.
4. If NFA of 6 states excluding the initial state is converted into DFA, maximum possible number of states for the DFA is ?
a) 64
b) 32
c) 128
d) 127
Answer
Answer: c [Reason:] The maximum number of sets for DFA converted from NFA would be not greater than 2n.
5. NFA, in its name has ’non-deterministic’ because of :
a) The result is undetermined
b) The choice of path is non-deterministic
c) The state to be transited next is non-deterministic
d) All of the mentioned
Answer
Answer: b [Reason:] Non deterministic or deterministic depends upon the definite path defined for the transition from one state to another or undefined(multiple paths).
6. Which of the following is correct proposition?
Statement 1: Non determinism is a generalization of Determinism.
Statement 2: Every DFA is automatically an NFA
a) Statement 1 is correct because Statement 2 is correct
b) Statement 2 is correct because Statement 2 is correct
c) Statement 2 is false and Statement 1 is false
d) Statement 1 is false because Statement 2 is false
Answer
Answer: b [Reason:] DFA is a specific case of NFA.
7. Given Language L= {xϵ {a, b}*|x contains aba as its substring}
Find the difference of transitions made in constructing a DFA and an equivalent NFA?
a) 2
b) 3
c) 4
d) Cannot be determined.
Answer
Answer: a [Reason:] The individual Transition graphs can be made and the difference of transitions can be determined.
8. The construction time for DFA from an equivalent NFA (m number of node)is:
a) O(m2)
b) O(2m)
c) O(m)
d) O(log m)
Answer
Answer: b [Reason:] From the coded NFA-DFA conversion.
9. If n is the length of Input string and m is the number of nodes, the running time of DFA is x that of NFA.Find x?
a) 1/m2
b) 2m
c) 1/m
d) log m
Answer
Answer: a [Reason:] Running time of DFA: O(n) and Running time of NFA =O(m2n).
10. Which of the following option is correct?
a) NFA is slower to process and its representation uses more memory than DFA
b) DFA is faster to process and its representation uses less memory than NFA
c) NFA is slower to process and its representation uses less memory than DFA
d) DFA is slower to process and its representation uses less memory than NFA
Answer
Answer: c [Reason:] NFA, while computing strings, take parallel paths, make different copies of input and goes along different paths in order to search for the result. This creates the difference in processing speed of DFA and NFA.
Set 3
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
Answer
Answer: b [Reason:] NP is said to be one of the most fundamental complexity classes. NP is an acronym for Non deterministic polynomial time.
2. The hardest of NP problems can be:
a) NP-complete
b) NP-hard
c) P
d) None of the mentioned
Answer
Answer: a [Reason:] NP class contains many important problems, the hardest of which is NP-complete, whose solution is sufficient to deal with any other NP problem in polynomial time.
3. Which of the following contains NP?
a) PSPACE
b) EXPSPACE
c) Both (a) and (b)
d) None of the mentioned
Answer
Answer: c [Reason:] It is sufficient to construct a PSPACE machine that loops over all proof strings and feeds each one to a polynomial time verifier. It is also contained in EXPTIME, since the same algorithm operates in exponential time.
4. Travelling sales man problem belongs to which of the class?
a) P
b) NP
c) Linear
d) None of the mentioned
Answer
Answer: b [Reason:] Travelling Salesman Problem: Given an input matrix of distances between n cities, this problem is to determine if there is a route visiting all cities with total distance less than k.
5. State true or false?
Statement: If a problem X is in NP and a polynomial time algorithm for X could also be used to solve problem Y in polynomial time, then Y is also in NP.
a) true
b) false
Answer
Answer: a [Reason:] This is just a commutative property of NP complexity class where a problem is said to be in NP if it can be solved using an algorithm which was used to solve another NP problem in polynomial amount of time.
6. A problem which is both _______ and _________ is said to be NP complete.
a) NP, P
b) NP, NP hard
c) P, P complete
d) None of the mentioned
Answer
Answer: a [Reason:] A problem is said to be NP Hard if an algorithm for solving the problem can be translated from for solving any other problem. It is easier to show a problem NP than showing it Np Hard.
7. Which of the following is incorrect for the given phrase
Phrase :’solvable by non deterministic algorithms in polynomial time’
a) NP Problems
b) During control flow, non deterministic algorithm may have more than one choice
c) If the choices that non deterministic algorithm makes are correct, the amount of time it takes is bounded by polynomial time.
d) None of the mentioned
Answer
Answer: d [Reason:] Primality testing is a simple example. To decide whether a number is prime or not, one simply selects non deterministically a number checks whether factors exist for the number or not.
8. In terms of NTIME, NP problems are the set of decision problems which can be solved using a non deterministic machine in _______ time.
a) O(n)
b) O(n1/2)
c) O(nk), k∈N
d) None of the mentioned
Answer
Answer: c [Reason:] The complexity class NP can be defined in terms of NTIME as:
NP=O(nk) for k ∈N.
9. Which of the following can be used to define NP complexity class?
a) Verifier
b) Polynomial time
c) Both (a) and (b)
d) None of the mentioned
Answer
Answer: c [Reason:] NP can be defined using deterministic turing machines as verifiers.
10. Which of the following are not in NP?
a) All problems in P
b) Boolean Satisfiability problems
c) Integer factorization problem
d) None of the mentioned
Answer
Answer: d [Reason:] This is a list of some problems which are in NP:
a) All problems in P
b) Decision version of Integer factorization method
c) Graph Isomorphism Problem
d) All NP complete problems, etc.
11. Which of the following does not belong to the closure properties of NP class?
a) Union
b) Concatenation
c) Reversal
d) Complement
Answer
Answer: d [Reason:] It is unknown about the closure property-complement for the complexity class NP. The question is so called NP versus co-NP problem.
Set 4
1. X is a simple mathematical model of a computer. X has unrestricted and unlimited memory. X is a FA with R/W head. X can have an infinite tape divided into cells, each cell holding one symbol.
Name X?
a) Push Down Automata
b) Non deterministic Finite Automata
c) Turing machines
d) None of the mentioned
Answer
Answer: c [Reason:] Turing machine is known as universal computer. It is denoted by M=(Q,Σ,Ґ ,δ ,q0, B,F)
2. Which of the following is/are not an application of turing machine?
a) Language Recognization
b) Computers of functions on non negative numbers
c) Generating devices
d) None of the mentioned
Answer
Answer: d [Reason:] A turing machine can have many applications like : Enumerator (A turing machine with an output printer), function computer, etc.
3. State true or false:
Statement: Turing Machine can change symbols on its tape, whereas the FA cannot change symbols on tape.
a) true
b) false
Answer
Answer: a [Reason:] The following mentioned is the difference between 2-way FA and TM. Another instance is that TM has a read/write tape head while FA doesn’t.
4. Which of the following cannot be a possibility of a TM while it processes an input?
a) Enters accepting state
b) Enters non-accepting state
c) Enters infinite loop and never halts
d) None of the mentioned
Answer
Answer: d [Reason:] The following mentioned are the only possibilities of operating a string through a turing machine.
5. Pick the odd one out.
a) Subroutines
b) Multiple tracks
c) Shifting over
d) Recursion
Answer
Answer: d [Reason:] Except Recursion, all the other options are techniques of Turing Machine construction which further includes, Checking off symbols and Storage in finite control.
6. Which among the following is not true for 2-way infinte TM?
a) tape in both directions
b) Leftmost square not distinguished
c) Any computation that can be performed by 2-way infinite tape can also be performed by standard TM.
d) None of the mentioned
Answer
Answer: d [Reason:] All of the mentioned are correct statements for a two way infinite tape turing machine. Theorems say the power of such a machine is in no way superior than a standard turing machine.
7. Can a turing machine act like a transducer?
a) yes
b) no
Answer
Answer: a [Reason:] A turing machine can be used as a transducer. The most obvious way to do this is to treat the entire non blank portion of the initial tape as input, and to treat the entire blank portion of the tape when the machine halts as output.
8. Which of the following does not exists?
a) Mutitape TM
b) Multihead TM
c) Multidimentional TM
d) None of the mentioned
Answer
Answer: d [Reason:] If the tape contains k-dimentional array of cells infinte in all 2k directions, for some fixed k and has a finite control, the machine can be called Multidimentional TM.
9. Enumerator is a turing machine with __________
a) an output printer
b) 5 input tapes
c) a stack
d) none of the mentioned
Answer
Answer: a [Reason:] Here, the turing machine can use the printer as an output device to print strings.
Note: There is no input to an enumerator. If it doesn’t halt, it may print an infinite set of strings.
10. For the following language, an enumerator will print:
L={anbn|n>=0}
a) anbn
b) {ab, a2b2, a3b3, …}
c) {e, ab, a2b2, a3b3, …}
d) None of the mentioned
Answer
Answer: b [Reason:] An enumerator is a turing machine with an output printer. It can use an printer as an output device to print output strings. As n also holds the value , epsilon will also be a part of the output set.
11. Complete the following statement:
Statement : A language is turing recognizable if an only if ___________
a) an enumerator enumerates it
b) it is finite
c) both (a) and (b)
d) none of the mentioned
Answer
Answer: a [Reason:] If an Enumerator E enumerates a language L, there is a turing machine M that recognizes language L. Also, If a turing machine M recognizes a language L, there is an enumerator for L.
Set 5
1. Which of the following conversion is not feasible?
a) Regular expression to automaton conversion
b) Automaton to Regular Expression Conversion
c) NFA to DFA
d) None of the mentioned
Answer
Answer: d [Reason:] Each of the four formats of representation of the regular language be it, DFA, NFA, Regular Expression or e-NFA can be converted to the rest three forms.
2. The computation of e-closure of n-states takes ______ time.
a) O(n2)
b) O(n3)
c) O(2n)
d) None of the mentioned
Answer
Answer: b [Reason:] We must search from each of the n states along all arcs labelled e. If there are n states, there can be no more than n2 states.
3. For a _________ state DFA, the time taken for DFA-NFA conversion is O(n).
a) n
b) n1/2
c) n2
d) 2n
Answer
Answer: a [Reason:] The conversion DFA to NFA is simple, and takes O(n) time on an n-state DFA.
4. With reference to Automaton to Regular Expression Conversion, for each of the n rounds, where n is the number of states of DFA, we can _________ the size of the regular expression constructed.
a) double
b) triple
c) quadruple
d) none of the mentioned
Answer
Answer: c [Reason:] We can quadruple the size of the regular expression per round. Thus, we can simply write n3 expressions can take time O(n34n), where n =number of states of the DFA.
5. Conversion of regular expression to e-NFA takes ___________ time.
a) linear
b) exponential
c) logarithmic
d) none of the mentioned
Answer
Answer: a [Reason:] It is possible to parse the expression efficiently, using a technique that takes only O(n) time on a expression of length n3.
6. The conversion of NFA to DFA can be done in:
a) exponential time
b) linear time
c) logarithmic time
d) all of the mentioned
Answer
Answer: a [Reason:] We can eliminate e-transitions from an n state epsilon-NFA to build an ordinary NFA in O(n3) time, without changing the number of states.Next, producing to DFA can take exponential time.
7. Which of the following cannot be converted in an ordinary NFA?
a) DFA
b) Regular Expression
c) e-NFA
d) None of the mentioned
Answer
Answer: d [Reason:] Each of the following can expressed in terms of ordinary NFA with different time complexities.
8. NFA to DFA conversion is done via
a) Subset Construction method
b) Warshalls Algorithm
c) Ardens theorem
d) None of the mentioned
Answer
Answer: a [Reason:] Powerset or subset construction method is a standard method for converting a non deterministic finite automata into DFA which recognizes the same formal language.
9. State true or false:
Statement: Regular expression can directly be converted to DFA without intermediate steps.
a) true
b) false
Answer
Answer: b [Reason:] There exists subsequent steps like formation of epsilon-NFA and NFA before the formation of corresponding DFA.
10. Is the following statement correct?
Statement: Thompson construction is used to convert Regular expression to finite automata.
a) Yes
b) No
Answer
Answer: a [Reason:] Thompson’s Construction is used to find out a Finite Automaton from a Regular Expression. We will reduce the regular expression into smallest regular expressions and convert them to NFA and finally to DFA.
