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
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
View Answer
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
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 = { 5. Which among the following are semi decidable? 6. The language accepted by a turing machine is called ____________ 7. Decidable can be taken as a synonym to: 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: 9. An algorithm is called efficient if it runs in ____________ time on a serial computer. 10. A problem is called __________ if its has an efficient algorithm for itself. 11. A formal language is recursive if : 12. Recursive languages are also known as: 13. The class of recursive language is known as: 14. Which of the following was not a part of Chomsky hierarchy? Sanfoundry Global Education & Learning Series – Automata Theory.
Fill in the blank:
Rec-DFA is ___________
a) Undecidable
b) Decidable
c) Non finite
d) None of the mentioned
View Answer
Explanation: Under decidablity of regular language properties we have the following lemma which states that A DFA which recognizes an input w is decidable.
a) Empty-DFA
b) Rec-NFA
c) Infinite-DFA
d) All of the mentioned
View Answer
Explanation: All are the properties of regular languages and all are decidable languages.
a) Recursive Ennumerable
b) Recursive
c) Recursive Ennumerable and Recursive
d) None of the mentioned
View Answer
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.
a) recursive
b) non recursive
c) recognizable
d) none of the mentioned
View Answer
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.
a) Decidable
b) Undecidable
c) Computable
d) None of the mentioned
View Answer
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.
a) polynomial
b) non polynomial
c) logarithmic
d) none of the mentioned
View Answer
Explanation: Example: Runtimes of efficient algorithms
O(n), O(nlogn), O(n3log2n)
Runtimes of inefficient algorithms
O(2n), O(n!)
a) tractable
b) intractable
c) computational
d) none of the mentioned
View Answer
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.
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
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.
a) decidable
b) undecidable
c) sometimes decidable
d) none of the mentioned
View Answer
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.
a) R
b) RC
c) RL
d) All of the mentioned
View Answer
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.
a) Context sensitive grammar
b) Unrestricted grammar
c) Recursive grammar
d) None of the mentioned
View Answer
Explanation: All recursive languages are recursively enumerable. All regular, context free and context sensitive languages are recursive.
To practice all areas of Automata Theory for Experienced people, here is complete set of 1000+ Multiple Choice Questions and Answers.
