Automata Theory Questions and Answers – The Universal Language-Undecidability

«
»

This set of Automata Theory Questions and Answers for Experienced people focuses on “The Universal Language-Undecidability”.

1. The decision problem is the function from string to ______________
a) char
b) int
c) boolean
d) none of the mentioned
View Answer

Answer: c
Explanation: The decision problem requires checking of input (string) has some property or not. That is a string to boolean transaction.
advertisement

2. A language L is said to be ____________ if there is a turing machine M such that L(M)=L and M halts at every point.
a) Turing acceptable
b) decidable
c) undecidable
d) none of the mentioned
View Answer

Answer: b
Explanation: Decidability refers to the decision problem and existence of a effective method for determining membership, and return true and false accordingly rather that going into a loop forever.

3. Which among the following are undecidable theories?
a) The first order theory of boolean algebra
b) The first order theory of Euclidean geomentry
c) The first order theory of hyperbolic geometry
d) The first order theory of the natural number with addition, multiplication, and equality
View Answer

Answer: d
Explanation: Tarski and Mostowski in 1949, established that the first order theory of natural numbers with addition, multiplication, and equality is an undecidable theory. Others mentioned are decidable theories.
Sanfoundry Certification Contest of the Month is Live. 100+ Subjects. Participate Now!
advertisement
advertisement

4. Rec-DFA = { | M is a DFA and M recognizes input w}.
Fill in the blank:
Rec-DFA is ___________
a) Undecidable
b) Decidable
c) Non finite
d) None of the mentioned
View Answer

Answer: b
Explanation: Under decidablity of regular language properties we have the following lemma which states that A DFA which recognizes an input w is decidable.

5. Which among the following are semi decidable?
a) Empty-DFA
b) Rec-NFA
c) Infinite-DFA
d) All of the mentioned
View Answer

Answer: d
Explanation: All are the properties of regular languages and all are decidable languages.
advertisement

6. The language accepted by a turing machine is called ____________
a) Recursive Ennumerable
b) Recursive
c) Recursive Ennumerable and Recursive
d) None of the mentioned
View Answer

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

7. Decidable can be taken as a synonym to:
a) recursive
b) non recursive
c) recognizable
d) none of the mentioned
View Answer

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

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

Answer: b
Explanation: 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.

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

Answer: a
Explanation: Example: Runtimes of efficient algorithms
O(n), O(nlogn), O(n3log2n)
Runtimes of inefficient algorithms
O(2n), O(n!)
advertisement

10. A problem is called __________ if its has an efficient algorithm for itself.
a) tractable
b) intractable
c) computational
d) none of the mentioned
View Answer

Answer: a
Explanation: A problem is called intractable if there is an efficient (i.e. polynomial time) algorithm that solves it. A problem is called intractable if there exists no efficient algorithm that solves it.

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

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

12. Recursive languages are also known as:
a) decidable
b) undecidable
c) sometimes decidable
d) none of the mentioned
View Answer

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

13. The class of recursive language is known as:
a) R
b) RC
c) RL
d) All of the mentioned
View Answer

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

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

Answer: c
Explanation: All recursive languages are recursively enumerable. All regular, context free and context sensitive languages are recursive.

Sanfoundry Global Education & Learning Series – Automata Theory.
To practice all areas of Automata Theory for Experienced people, here is complete set of 1000+ Multiple Choice Questions and Answers.

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 & technical discussions at Telegram SanfoundryClasses.