Question
a.
Diagonalization
b.
Recursive Induction
c.
both a and b
d.
None of the mentioned
Posted under Formal Languages and Automata Theory
Engage with the Community - Add Your Comment
Confused About the Answer? Ask for Details Here.
Know the Explanation? Add it Here.
Q. Which of the following technique is used to find whether a natural language isnt recursive ennumerable?
Similar Questions
Discover Related MCQs
Q. Diagonalization can be useful in:
View solution
Q. Which of the following are undecidable problems?
View solution
Q. Which of the following are incorrect options?
View solution
Q. If a problem has an algorithm to answer it, we call it _________
View solution
Q. Which of the following are decidable problems?
View solution
Q. Which one of the following is true for the given?
A={(M,w)|M is a turing machine that accepts string w}
View solution
Q. Statement: If L id R.E., L^c needs to be R.E. Is it correct?
View solution
Q. Which of the following is true for The Halting problem?
View solution
Q. With reference to binary strings, state true or false:
Statement: For any turing machine, the input alphabet is restricted to {0,1}.
View solution
Q. 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.
View solution
Q. The decision problem is the function from string to ______________
View solution
Q. 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.
View solution
Q. Which aong the following are undecidable theories?
View solution
Q. Rec-DFA = { | M is a DFA and M recognizes input w}.
Fill in the blank:
Rec-DFA is ___________
View solution
Q. Which among the following are semi decidable?
View solution
Q. The language accepted by a turing machine is called ____________
View solution
Q. Decidable can be taken as a synonym to:
View solution
Q. 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:
View solution
Q. An algorithm is called efficient if it runs in ____________ time on a serial computer.
View solution
Q. A problem is called __________ if its has an efficient algorithm for itself.
View solution
Suggested Topics
Are you eager to expand your knowledge beyond Formal Languages and Automata Theory? We've curated a selection of related categories that you might find intriguing.
Click on the categories below to discover a wealth of MCQs and enrich your understanding of Computer Science. Happy exploring!
Java Programming
Level up your coding skills with our Java Programming MCQs. From object-oriented...
Microprocessor
Understand the heart of your computer with our Microprocessor MCQs. Topics include...