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
View Answer

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

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

Answer: c
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.
advertisement
advertisement

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

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

Answer: a
Explanation: An algorithm is a TM that halts on all inputs,accepted or not. Putting other way, decidable problems are recursive languages.
Sanfoundry Certification Contest of the Month is Live. 100+ Subjects. Participate Now!

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

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

Answer: d
Explanation: We can proof A to be undecidable using the contradiction method.
advertisement

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

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

Answer: b
Explanation: Any recursive enumerable language is not closed under complementation.
advertisement

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

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

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

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

If you find a mistake in question / option / answer, kindly take a screenshot and email to [email protected]

advertisement
advertisement
Subscribe to our Newsletters (Subject-wise). Participate in the Sanfoundry Certification contest to get free Certificate of Merit. Join our social networks below and stay updated with latest contests, videos, internships and jobs!

Youtube | Telegram | LinkedIn | Instagram | Facebook | Twitter | Pinterest
Manish Bhojasia - Founder & CTO at Sanfoundry
Manish Bhojasia, a technology veteran with 20+ years @ Cisco & Wipro, is Founder and CTO at Sanfoundry. He lives in Bangalore, and focuses on development of Linux Kernel, SAN Technologies, Advanced C, Data Structures & Alogrithms. Stay connected with him at LinkedIn.

Subscribe to his free Masterclasses at Youtube & discussions at Telegram SanfoundryClasses.