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

Q. A formal language is recursive if :

View solution

Q. Recursive languages are also known as:

View solution

Q. The class of recursive language is known as:

View solution

Q. Which of the following was not a part of Chomsky hierarchy ?

View solution

Q. According to the rice’s theorem, If P is a non trivial property, Lp is :

View solution

Q. Fill in the blank with reference to Rice’s theorem.
For any non-trivial property of __________ no general or effective method can decide whether an algorithm computes it with that property.

View solution