250+ TOP MCQs on The Diagonalization Languages and Answers

Automata Theory Multiple Choice Questions on “The Diagonalization Languages”

1. Which of the following technique is used to find whether a natural language isnt recursive ennumerable?
a) Diagonalization
b) Recursive Induction
c) Both (a) and (b)
d) None of the mentioned

Answer: a
Clarification: To find a non recursively ennumerable language, we use the technique of diagonalization.

2. Diagonalization can be useful in:
a) To find a non recursively ennumerable language
b) To prove undecidablility of haltig problem
c) Both (a) and (b)
d) None of the mentioned

Answer: c
Clarification: Diagonalization is a technique we use for the following operations:
a) To find a non recursively ennumerable language.
b) To prove undecidablility 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) Both (a) and (b)
d) None of the mentioned

Answer: c
Clarification: 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) Both (a) and (b)
d) None of the mentioned

Answer: d
Clarification: 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

Answer: a
Clarification: 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

Answer: d
Clarification: 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

Answer: d
Clarification: 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 that are guaranteed to halt only on acceptance are recursive ennumerable.
c) Both (a) and (b)
d) None of the mentioned

Answer: c
Clarification: There are two types of TMs on the basis of halting: Recursive and Recursively Ennumerable(TM may or may not halt,could loop forever).

9. Statement: If L id R.E., L^c needs to be R.E. Is it correct?
a) Yes
b) No
c) Maybe
d) Cannot predict

Answer: b
Clarification: Any recursive ennumerable language is not closed under complementation.

10. Which of the following is true for The Halting problem?
a) It is recursively ennumerable
b) It is undecidable
c) Both (a) and (b)
d) None of the mentioned

Answer: c
Clarification: 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

Answer: a
Clarification: 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

Answer: a
Clarification: 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.