Theory Of Computation Set 1
On This Page
This set of Theory of Computation Multiple Choice Questions & Answers (MCQs) focuses on Theory Of Computation Set 1
Q1 | What is the reason behind a Turing machine is more powerful than finite state machine FSM?
- turing machine head movement is continued to one direction.
- turing machine head moment is in both directions i.e. left moment and right moment as well.
- turing machine has capability remember arbitrary long sequence of input string.
- all are correct.
Q2 | A pushdown automata behaves like a Turing machine, when it has number of auxiliary/ memory.
- 0
- exectly 2
- 2 or more
- both exectly 2 or more are correct
Q3 | The language L = {anbnan n≥ 1} is recognized by
- turing machine
- 2 pushdown automata
- post machine
- all are correct
Q4 | If Turing machine accepts all the words of the languages L and rejects or loops for other words, which are not in L, then L is said to be
- recursive enumerable
- recursive
- context free language (cfl)
- none of them
Q5 | If a Turing machine halts for each and every world of a language L and rejects other, then L is said to be
- recursive enumerable
- recursive
- context free language
- none of these
Q6 | Universal Turing machine (UTM) influenced the concepts of
- computability
- interpretive implementation of programming language
- program and data is in same memory
- all are correct
Q7 | The number of symbols necessary to simulate a Turing machine with m symbols and n states
- 4m × n + m
- 4m × n + n
- m+n
- none of them
Q8 | A universal Turing machine is a
- reprogrammable truing machine
- two-tape turing machine
- single tape turing machine
- none of them
Q9 | He difference between a read-only Turing machine and a two-way finite state machine is
- head movement
- finite control
- storage capacity
- power
Q10 | Which is correct regard an off-line Truing machine?
- an offline turing machine is a special type of multi-tape turing machine
- an offline turing machine is a kind of multi-tracks truing machine
- an offline turing machine is a kind of single-track turing machine
- none of them
Q11 | Which of the following statement is wrong?
- power of ntm and tm is same
- for n ≥ 2, npda has some power as a tm
- for n ≥ 2, npda and 2pda have same power
- power of ntm and tm is not same
Q12 | Four pairs are following; in each pair both objects have some common thing. Choose the odd pair;
- (tm, 2pda)
- (computer, utm)
- (2pda, npda)
- (fa, pda)
Q13 | We think of a Turing machine’s transition function as a
- computer system
- software
- hardware
- all of them
Q14 | Church’s Thesis supports
- a turing machine as a general-purpose computer system
- a turing machine an algorithm and an algorithm as a turing machine
- both tm is an general-purpose computer and tm is an algorithm and vice-versa are correct
- none of them is correct
Q15 | A random access machine (RAM) and truing machine are different in
- power
- accessing
- storage
- both accessing and storage are correct
Q16 | Choose the correct statement
- recursive set ⊆ recursive enumerable set
- total function is same as partial function
- recursive sets are analogous to total functions
- both recursive set ⊆ recursive enumerable set and recursive sets are analogous to total functions are correct.
Q17 | Given S = {a, b}, which one of the following sets is not countable?
- the set all strings over Σ
- the set of all language over Σ
- the set of all binary strings
- the set of all languages over Σ accepted by turing machines
Q18 | In which of the stated below is the following statement true?“For every non-deterministic machine M1, there exists as equivalent deterministic machine M2 recognizing the same language.”
- m1 is a non-deterministic finite automata
- m1 is a non-deterministic push-down automata
- m1 is a non-deterministic turing machine
- for no machine m1 use the above statement true
Q19 | Which of the following conversion is not possible (algorithmically)?
- regular grammar to context-free grammar
- non-deterministic finite state automata to deterministic finite state automata
- non-deterministic pushdown automata to deterministic pushdown automata
- none deterministic turing machine to deterministic turing machine
Q20 | 0
- L1 is regular but not L2
- L2 is regular but not L1
- Both L1 and L2 are regular
- Neither L1 nor L2 are regular
Q21 | A spanning tree for a simple graph of order 24 has
- 12 edges
- 6 edges
- 23 edges
- None of above.
Q22 | If G is a simple connected 3-regular planar graph where every region isbounded by exactly 3 edges, then the edges of G is
- 3
- 4
- 6
- 5
Q23 | If G is a connected planar graph of v vertices e edges and r regions then
- v-e+r=2
- e-v+r=2
- v+e-r=2
- None of above.
Q24 | A Hamiltonian cycle in a Hamiltonian graph of order 24 has
- 12 edges.
- 24 edges
- 23 edges
- None of above.
Q25 | If G is a simple connected 3-regular planar graph where every region is bounded by exactly 3 edges, then the edges of G is
- 3
- 4
- 6
- 5