1. Which among the following are semi decidable?
a) Empty-DFA
b) Rec-NFA
c) Infinite-DFA
d) All of the mentioned
Answer: d
Clarification: All are the properties of regular languages and all are decidable languages.
2. The language accepted by a turing machine is called ____________
a) Recursive Ennumerable
b) Recursive
c) Both (a) and (b)
d) None of the mentioned
Answer: c
Clarification: The language accepted by Turing machines are called recursively ennumerable (RE), and the subset of RE languages that are accepted by a turing machine that always halts are called recursive.
3. Decidable can be taken as a synonym to:
a) recursive
b) non recursive
c) recognizable
d) none of the mentioned
Answer: a
Clarification: We can refer to languages as ‘recursive’ and problems as ‘decidable’. If a language is not recursive , then we call the problem expressed by that language undecidable.
4. The problems which have no algorithm, regardless of whether or not they are accepted by a turing machine that fails to halts on some input are referred as:
a) Decidable
b) Undecidable
c) Computable
d) None of the mentioned
Answer: b
Clarification: The problems that can be solved by a turing machine can divided into two classes:
a) Those that have an algorithm
b) Intractable problems: Those that are only solved by a turing machine that may run forever on inputs they do not accept.
5. An algorithm is called efficient if it runs in ____________ time on a serial computer.
a) polynomial
b) non polynomial
c) logarithmic
d) none of the mentioned
Answer: a
Clarification: Example: Runtimes of efficient algorithms
O(n), O(nlogn), O(n3log2n)
Runtimes of inefficient algorithms
O(2n), O(n!)
6. A problem is called __________ if its has an efficient algorithm for itself.
a) tractable
b) intractable
c) computational
d) none of the mentioned
Answer: a
Clarification: A problem is called intractable iff there is an efficient (i.e. polynomial time) algorithm that solves it. A problem is called intractable iff there exists no efficient algorithm that solves it.
7. A formal language is recursive if :
a) a total turing machine exists
b) a turing machine that halts for every input
c) turing machine rejects if the input does not belong to the language
d) all of the mentioned
Answer: d
Clarification: A formal language is called recursive if it is a recursive subset of the set of all possible finite sequences over the alphabet of the language.
8. Recursive languages are also known as:
a) decidable
b) undecidable
c) sometimes decidable
d) none of the mentioned
Answer: a
Clarification: A language is recursive if there exists a turing machine such that it halts i.e. accepts if the input belongs to the language else rejects. It is better called Turing decidable language.
9. The class of recursive language is known as:
a) R
b) RC
c) RL
d) All of the mentioned
Answer: a
Clarification: 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.
10. 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
Answer: c
Clarification: All recursive languages are recursively enumerable. All regular, context free and context sensitive languages are recursive.