# 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

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

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

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

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.

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

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

Explanation: All are the properties of regular languages and all are decidable languages.
Sanfoundry Certification Contest of the Month is Live. 100+ Subjects. Participate Now!

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

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

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.

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

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

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

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

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

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

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

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

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.

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