# Automata Theory Questions and Answers – The Diagonalization Languages

«
»

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

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

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

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.
Sanfoundry Certification Contest of the Month is Live. 100+ Subjects. Participate Now!

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

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

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

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

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

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

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

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

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

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. 