Rec-DFA = { | M is a DFA and M recognizes input w}.Fill in the blank:Rec-DFA is ___________a) Undecidableb) Decidablec) Non finited) None of the mentionedAnswer: bExplanation: 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-DFAb) Rec-NFAc) Infinite-DFAd) All of the mentionedAnswer: d Explanation: All are the properties of regular languages and all are decidable languages.advertisement/**/ var adpushup = adpushup || {}; adpushup.que = adpushup.que || []; adpushup.que.push(function() { adpushup.triggerAd("fdd9bf87-4faf-4493-82b4-e5538b31931a"); });/**/6. The language accepted by a turing machine is called ____________a) Recursive Ennumerableb) Recursivec) Both (a) and (b)d) None of the mentionedAnswer: cExplanation: 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) recursiveb) non recursivec) recognizabled) none of the mentionedAnswer: aExplanation: 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/**/ var adpushup = adpushup || {}; adpushup.que = adpushup.que || []; adpushup.que.push(function() { adpushup.triggerAd("21eae76a-c83f-42b0-aec5-01d590a53f37"); });/**/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) Decidableb) Undecidablec) Computabled) None of the mentionedAnswer: bExplanation: The problems that can be solved by a turing machine can divided into two classes:a) Those that have an algorithmb) 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) polynomialb) non polynomialc) logarithmicd) none of the mentionedAnswer: aExplanation: Example: Runtimes of efficient algorithmsO(n), O(nlogn), O(n3log2n)Runtimes of inefficient algorithmsO(2n), O(n!)advertisement/**/ var adpushup = adpushup || {}; adpushup.que = adpushup.que || []; adpushup.que.push(function() { adpushup.triggerAd("90f55663-effd-4105-b1e7-29d86b526544"); });/**/10. A problem is called __________ if its has an efficient algorithm for itself.a) tractableb) intractablec) computationald) none of the mentionedAnswer: aExplanation: A problem is called intractable iff there is an efficient (i.e. polynomial time) algorithm that solves it. A problem is called intractable iff there exists no efficient algorithm that solves it.11. A formal language is recursive if :a) a total turing machine existsb) a turing machine that halts for every inputc) turing machine rejects if the input does not belong to the languaged) all of the mentionedAnswer: dExplanation: 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) decidableb) undecidablec) sometimes decidabled) none of the mentionedAnswer: aExplanation: 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) Rb) RCc) RLd) All of the mentionedAnswer: aExplanation: 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. Undecidableb) Decidablec) Non finited) None of the mentionedAnswer: bExplanation: 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-DFAb) Rec-NFAc) Infinite-DFAd) All of the mentionedAnswer: d Explanation: All are the properties of regular languages and all are decidable languages.advertisement/**/ var adpushup = adpushup || {}; adpushup.que = adpushup.que || []; adpushup.que.push(function() { adpushup.triggerAd("fdd9bf87-4faf-4493-82b4-e5538b31931a"); });/**/6. The language accepted by a turing machine is called ____________a) Recursive Ennumerableb) Recursivec) Both (a) and (b)d) None of the mentionedAnswer: cExplanation: 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) recursiveb) non recursivec) recognizabled) none of the mentionedAnswer: aExplanation: 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/**/ var adpushup = adpushup || {}; adpushup.que = adpushup.que || []; adpushup.que.push(function() { adpushup.triggerAd("21eae76a-c83f-42b0-aec5-01d590a53f37"); });/**/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) Decidableb) Undecidablec) Computabled) None of the mentionedAnswer: bExplanation: The problems that can be solved by a turing machine can divided into two classes:a) Those that have an algorithmb) 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) polynomialb) non polynomialc) logarithmicd) none of the mentionedAnswer: aExplanation: Example: Runtimes of efficient algorithmsO(n), O(nlogn), O(n3log2n)Runtimes of inefficient algorithmsO(2n), O(n!)advertisement/**/ var adpushup = adpushup || {}; adpushup.que = adpushup.que || []; adpushup.que.push(function() { adpushup.triggerAd("90f55663-effd-4105-b1e7-29d86b526544"); });/**/10. A problem is called __________ if its has an efficient algorithm for itself.a) tractableb) intractablec) computationald) none of the mentionedAnswer: aExplanation: A problem is called intractable iff there is an efficient (i.e. polynomial time) algorithm that solves it. A problem is called intractable iff there exists no efficient algorithm that solves it.11. A formal language is recursive if :a) a total turing machine existsb) a turing machine that halts for every inputc) turing machine rejects if the input does not belong to the languaged) all of the mentionedAnswer: dExplanation: 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) decidableb) undecidablec) sometimes decidabled) none of the mentionedAnswer: aExplanation: 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) Rb) RCc) RLd) All of the mentionedAnswer: aExplanation: 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. Decidablec) Non finited) None of the mentionedAnswer: bExplanation: 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-DFAb) Rec-NFAc) Infinite-DFAd) All of the mentionedAnswer: d Explanation: All are the properties of regular languages and all are decidable languages.advertisement/**/ var adpushup = adpushup || {}; adpushup.que = adpushup.que || []; adpushup.que.push(function() { adpushup.triggerAd("fdd9bf87-4faf-4493-82b4-e5538b31931a"); });/**/6. The language accepted by a turing machine is called ____________a) Recursive Ennumerableb) Recursivec) Both (a) and (b)d) None of the mentionedAnswer: cExplanation: 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) recursiveb) non recursivec) recognizabled) none of the mentionedAnswer: aExplanation: 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/**/ var adpushup = adpushup || {}; adpushup.que = adpushup.que || []; adpushup.que.push(function() { adpushup.triggerAd("21eae76a-c83f-42b0-aec5-01d590a53f37"); });/**/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) Decidableb) Undecidablec) Computabled) None of the mentionedAnswer: bExplanation: The problems that can be solved by a turing machine can divided into two classes:a) Those that have an algorithmb) 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) polynomialb) non polynomialc) logarithmicd) none of the mentionedAnswer: aExplanation: Example: Runtimes of efficient algorithmsO(n), O(nlogn), O(n3log2n)Runtimes of inefficient algorithmsO(2n), O(n!)advertisement/**/ var adpushup = adpushup || {}; adpushup.que = adpushup.que || []; adpushup.que.push(function() { adpushup.triggerAd("90f55663-effd-4105-b1e7-29d86b526544"); });/**/10. A problem is called __________ if its has an efficient algorithm for itself.a) tractableb) intractablec) computationald) none of the mentionedAnswer: aExplanation: A problem is called intractable iff there is an efficient (i.e. polynomial time) algorithm that solves it. A problem is called intractable iff there exists no efficient algorithm that solves it.11. A formal language is recursive if :a) a total turing machine existsb) a turing machine that halts for every inputc) turing machine rejects if the input does not belong to the languaged) all of the mentionedAnswer: dExplanation: 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) decidableb) undecidablec) sometimes decidabled) none of the mentionedAnswer: aExplanation: 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) Rb) RCc) RLd) All of the mentionedAnswer: aExplanation: 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 grammarb) Unrestricted grammar
• C. Non finited) None of the mentionedAnswer: bExplanation: 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-DFAb) Rec-NFAc) Infinite-DFAd) All of the mentionedAnswer: d Explanation: All are the properties of regular languages and all are decidable languages.advertisement/**/ var adpushup = adpushup || {}; adpushup.que = adpushup.que || []; adpushup.que.push(function() { adpushup.triggerAd("fdd9bf87-4faf-4493-82b4-e5538b31931a"); });/**/6. The language accepted by a turing machine is called ____________a) Recursive Ennumerableb) Recursivec) Both (a) and (b)d) None of the mentionedAnswer: cExplanation: 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) recursiveb) non recursivec) recognizabled) none of the mentionedAnswer: aExplanation: 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/**/ var adpushup = adpushup || {}; adpushup.que = adpushup.que || []; adpushup.que.push(function() { adpushup.triggerAd("21eae76a-c83f-42b0-aec5-01d590a53f37"); });/**/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) Decidableb) Undecidablec) Computabled) None of the mentionedAnswer: bExplanation: The problems that can be solved by a turing machine can divided into two classes:a) Those that have an algorithmb) 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) polynomialb) non polynomialc) logarithmicd) none of the mentionedAnswer: aExplanation: Example: Runtimes of efficient algorithmsO(n), O(nlogn), O(n3log2n)Runtimes of inefficient algorithmsO(2n), O(n!)advertisement/**/ var adpushup = adpushup || {}; adpushup.que = adpushup.que || []; adpushup.que.push(function() { adpushup.triggerAd("90f55663-effd-4105-b1e7-29d86b526544"); });/**/10. A problem is called __________ if its has an efficient algorithm for itself.a) tractableb) intractablec) computationald) none of the mentionedAnswer: aExplanation: A problem is called intractable iff there is an efficient (i.e. polynomial time) algorithm that solves it. A problem is called intractable iff there exists no efficient algorithm that solves it.11. A formal language is recursive if :a) a total turing machine existsb) a turing machine that halts for every inputc) turing machine rejects if the input does not belong to the languaged) all of the mentionedAnswer: dExplanation: 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) decidableb) undecidablec) sometimes decidabled) none of the mentionedAnswer: aExplanation: 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) Rb) RCc) RLd) All of the mentionedAnswer: aExplanation: 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 grammarb) Unrestricted grammarc) Recursive grammar
• D. None of the mentionedAnswer: bExplanation: 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-DFAb) Rec-NFAc) Infinite-DFAd) All of the mentionedAnswer: d Explanation: All are the properties of regular languages and all are decidable languages.advertisement/**/ var adpushup = adpushup || {}; adpushup.que = adpushup.que || []; adpushup.que.push(function() { adpushup.triggerAd("fdd9bf87-4faf-4493-82b4-e5538b31931a"); });/**/6. The language accepted by a turing machine is called ____________a) Recursive Ennumerableb) Recursivec) Both (a) and (b)d) None of the mentionedAnswer: cExplanation: 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) recursiveb) non recursivec) recognizabled) none of the mentionedAnswer: aExplanation: 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/**/ var adpushup = adpushup || {}; adpushup.que = adpushup.que || []; adpushup.que.push(function() { adpushup.triggerAd("21eae76a-c83f-42b0-aec5-01d590a53f37"); });/**/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) Decidableb) Undecidablec) Computabled) None of the mentionedAnswer: bExplanation: The problems that can be solved by a turing machine can divided into two classes:a) Those that have an algorithmb) 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) polynomialb) non polynomialc) logarithmicd) none of the mentionedAnswer: aExplanation: Example: Runtimes of efficient algorithmsO(n), O(nlogn), O(n3log2n)Runtimes of inefficient algorithmsO(2n), O(n!)advertisement/**/ var adpushup = adpushup || {}; adpushup.que = adpushup.que || []; adpushup.que.push(function() { adpushup.triggerAd("90f55663-effd-4105-b1e7-29d86b526544"); });/**/10. A problem is called __________ if its has an efficient algorithm for itself.a) tractableb) intractablec) computationald) none of the mentionedAnswer: aExplanation: A problem is called intractable iff there is an efficient (i.e. polynomial tim
• E. algorithm that solves it. A problem is called intractable iff there exists no efficient algorithm that solves it.11. A formal language is recursive if :a) a total turing machine existsb) a turing machine that halts for every inputc) turing machine rejects if the input does not belong to the languaged) all of the mentionedAnswer: dExplanation: 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) decidableb) undecidablec) sometimes decidabled) none of the mentionedAnswer: aExplanation: 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) Rb) RCc) RLd) All of the mentionedAnswer: aExplanation: 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 grammarb) Unrestricted grammarc) Recursive grammard) None of the mentionedAnswer: cExplanation: 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.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!Telegram | Youtube | LinkedIn | Instagram | Facebook | Twitter | PinterestYoutube | LinkedIn | Instagram | Facebook | Twitter | Pinterest« Prev - Automata Theory Questions and Answers – The Diagonalization Languages» Next - Automata Theory Questions and Answers – Rice’s Theorem, Properties and PCP