MCQ Computer Science

# Automata Theory Multiple Choice Question & Answers (MCQs) set-4

1. A turing machine has ____________ number of states in a CPU.
a) finite
b) infinte
c) May be finite
d) None of the mentioned

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).

2. Suppose we have a simple computer with control unit holding a PC with a 32 bit address + Arithmetic unit holding one double length 64 bit Arithmetic Register. The number of states the finite machine will hold:
a) 2(32*64)
b) 296
c) 96
d) 32

Explanation: According to the statistics of the question, we will have a finite machine with 2^96 states.

3. A regular language over an alphabet ? is one that cannot be obtained from the basic languages using the operation
a) Union
b) Concatenation
c) Kleene*
d) All of the mentioned

Explanation: Union, Intersection, Concatenation, Kleene*, Reverse are all the closure properties of Regular Language.

4. Statement 1: A Finite automata can be represented graphically; Statement 2: The nodes can be its states; Statement 3: The edges or arcs can be used for transitions
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

Explanation: It is possible to represent a finite automaton graphically, with nodes for states, and arcs for transitions.

5. Which of the following is not a Non deterministic turing machine?
a) Alternating Turing machine
b) Probabalistic Turing machine
d) None of the mentioned

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.

6. Which of the turing machines have existential and universal states?
a) Alternating Turing machine
b) Probalistic Turing machine
d) None of the mentioned

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.

7. Can a turing machine act like a transducer?
a) yes
b) no

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.

8. Which of the following does not exists?
a) Mutitape TM
c) Multidimentional TM
d) None of the mentioned

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.

9. A two-way infinite tape turing machine is ________ superior than the basic model of the turing machine in terms of power.
a) more
b) less
c) no way
d) none of the mentioned

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

Answer: There exists some computational languages which are not turing complete. Regular language which is accepted by finite automata tops the list. Other examples are pixel shader languages embedded in Direct3D and OpenGL extensions.

11. With reference to binary strings, state true or false:
Statement: For any turing machine, the input alphabet is restricted to {0,1}.
a) true
b) false

Explanation: When turing machines are coded as Binary strings, we are restricted to take any input alphabet except {0,1}.

12. With reference ti enumeration of binary strings, the conversion of binary strings to integer is possible by treating the resulting string as a base ____ integer.
a) 2
b) 8
c) 16
d) All of the mentioned

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.
13. The class of recursive language is known as:
a) R
b) RC
c) RL
d) All of the mentioned

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.

14. Which of the following was not a part of Chomsky hierarchy ?
a) Context sensitive grammar
b) Unrestricted grammar
c) Recursive grammar
d) None of the mentioned
[/toggle]