1. A turing machine has ____________ number of states in a CPU.
a) finite
b) infinte
c) May be finite
d) None of the mentioned
View Answer
Answer: a
Explanation: A turing machine has finite number of states in its CPU. However the states are not small in number. Real computer consist of registers which can store values (fixed number of bits).
a) 2(32*64)
b) 296
c) 96
d) 32
View Answer
Answer: b
Explanation: According to the statistics of the question, we will have a finite machine with 2^96 states.
a) Union
b) Concatenation
c) Kleene*
d) All of the mentioned
View Answer
Answer: d
Explanation: Union, Intersection, Concatenation, Kleene*, Reverse are all the closure properties of Regular Language.
Hint: Nodes and Edges are for trees and forests too.
Which of the following make the correct combination?
a) Statement 1 is false but Statement 2 and 3 are correct
b) Statement 1 and 2 are correct while 3 is wrong
c) None of the mentioned statements are correct
d) All of the mentioned
View Answer
Answer: d
Explanation: It is possible to represent a finite automaton graphically, with nodes for states, and arcs for transitions.
a) Alternating Turing machine
b) Probabalistic Turing machine
c) Read-only turing machine
d) None of the mentioned
View Answer
Answer: c
Explanation: 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.
a) Alternating Turing machine
b) Probalistic Turing machine
c) Read-only turing machine
d) None of the mentioned
View Answer
Answer: a
Explanation: 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.
a) yes
b) no
View Answer
Answer: a
Explanation: 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.
a) Mutitape TM
b) Multihead TM
c) Multidimentional TM
d) None of the mentioned
View Answer
Answer: d
Explanation: 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.
a) more
b) less
c) no way
d) none of the mentioned
View Answer
Explanation: A two way infinite tape turing machine is a turing machine with its input tape infinte in both directions, the other component being the same as the basic model.
10. Which of the following a Non-turing Complete language?
a) Regular Language
b) Context free grammars
c) Epigram
d) All of the mentioned
View Answer
Statement: For any turing machine, the input alphabet is restricted to {0,1}.
a) true
b) false
View Answer
Explanation: When turing machines are coded as Binary strings, we are restricted to take any input alphabet except {0,1}.
a) 2
b) 8
c) 16
d) All of the mentioned
View Answer
Explanation: It makes sense to talk about the i-th binary string” and about “the i-th Turing machine. If i makes no sense as a TM, assume the i-th TM accepts nothing.
a) R
b) RC
c) RL
d) All of the mentioned
View Answer
Explanation: R is the set of all recursive languages, a class of decision problems solvable by turing machines. Although, R is also used for the class RP.
a) Context sensitive grammar
b) Unrestricted grammar
c) Recursive grammar
d) None of the mentioned
[/toggle]
View Answer
Explanation: All recursive languages are recursively enumerable. All regular, context free and context sensitive languages are recursive.
a) infinite
b) decidable
c) undecidable
d) none of the mentioned
View Answer
Explanation: Rice’s theorem states that ‘Any non trivial property about the language recognized by a turing machine is undecidable’.
