This set of Automata Theory Multiple Choice Questions & Answers (MCQs) focuses on “The Diagonalization Languages”
1. Which of the following technique is used to find whether a natural language isn’t recursive enumerable?
a) Diagonalization
b) Recursive Induction
c) All of the mentioned
d) None of the mentioned
View Answer
Explanation: To find a non recursively enumerable language, we use the technique of diagonalization.
2. Diagonalization can be useful in:
a) To find a non recursively enumerable language
b) To prove undecidability of haltig problem
c) To find a non recursively enumerable language & also proves undecidability of haltig problem
d) None of the mentioned
View Answer
Explanation: Diagonalization is a technique we use for the following operations:
a) To find a non recursively enumerable language.
b) To prove undecidability of halting problem.
3. Which of the following are undecidable problems?
a) Determining whether two grammars generate the same language
b) Determining whether a grammar is ambiguous
c) Determining whether a grammar is ambiguous and two grammars generate the same language
d) None of the mentioned
View Answer
Explanation: In contrast we can put up an algorithm for checking whether two FA’s are equivalent and this program can be implemented as a program.
4. Which of the following are incorrect options?
a) Informally, problem is a yes/no question about an infinite set of possible instances
b) Formally, a problem is a language
c) All of the mentioned
d) None of the mentioned
View Answer
Explanation: Example: Does a graph G has a Hamilton cycle?
=>Each undirected graph is an instance of Hamilton cycle problem.
5. If a problem has an algorithm to answer it, we call it _________
a) decidable
b) solved
c) recognizable
d) none of the mentioned
View Answer
Explanation: An algorithm is a TM that halts on all inputs,accepted or not. Putting other way, decidable problems are recursive languages.
6. Which of the following are decidable problems?
a) Can a particular line of code in a program ever be executed?
b) Do two given CFG’s generate the same language
c) Is a given CFG ambiguous?
d) None of the mentioned
View Answer
Explanation: All of the mentioned problems are undecidable.
7.Which one of the following is true for the given?
A={(M,w)|M is a turing machine that accepts string w}
a) A concrete undecidable problem
b) A is recognizable but not decidable
c) -A is not recognizable
d) All of the mentioned
View Answer
Explanation: We can proof A to be undecidable using the contradiction method.
8. Which of the following are correct statements?
a) TMs that always halt are known as Decidable problems
b) TMs are not guaranteed to halt only on acceptance are recursive enumerable
c) All of the mentioned
d) None of the mentioned
View Answer
Explanation: There are two types of TMs on the basis of halting: Recursive and Recursively Enumerable(TM may or may not halt, could loop forever).
9. Statement: If L id R.E., Lc needs to be R.E. Is it correct?
a) Yes
b) No
c) Maybe
d) Cannot predict
View Answer
Explanation: Any recursive enumerable language is not closed under complementation.
10. Which of the following is true for The Halting problem?
a) It is recursively enumerable
b) It is undecidable
c) It is recursively enumerable and undecidable
d) None of the mentioned
View Answer
Explanation: Halting problem: Does a given Turing machine M halt on a given input w?
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
View Answer
Explanation: When turing machines are coded as Binary strings, we are restricted to take any input alphabet except {0,1}.
12. With reference to 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
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.
Sanfoundry Global Education & Learning Series – Automata Theory.
To practice all areas of Automata Theory, here is complete set of 1000+ Multiple Choice Questions and Answers.
- Apply for Computer Science Internship
- Check Automata Theory Books
- Practice Computer Science MCQs
- Check Computer Science Books
