1 Crore+ students have signed up on EduRev. Have you? 
Which of the following functions are computable with Turning Machine?
All the above functions are total recursive functions. The total recursive functions are like recursive language. Turing machine halts on each and every input of recursive language. All of the above functions are turing computable.
A countable union of countable sets is not
A countable union of countable set is countable. Countably infinite and denumerable are alternate names of countable sets.
∑* over {0,1} and 2^{∑*} are respectively,
Since ∑* is all the combinations of 0 and 1 and yet it is enumerable and belongs to the category of countably infinite. But 2^{∑*} is the power set of ∑* which is infinite. By diagonalisation theorem, power set of any countably infinite set is always uncountable, hence 2^{∑*} belongs to uncountably infinite set.
Which of the following is undecidable?
According to the decision properties of the CFL and Regular languages, Equivalence of regular languages and emptiness of regular languages are decidable. Also the finiteness of CFL is decidable. For each of above property an algorithm exist. But no algorithm exist for checking the equivalence of the two contextfree language.
The statement "ATM can’t solve halting problem’’ is
ATM cannot solves the halting problem because it cannot find in finite time that for the given word the machine will halt or not.
A PDA behaves like a TM when the number of auxiliary memory it has, is
Auxiliary memory = memory used by the machine for calculations or swappings.
PDA with 2 or more stacks is equivalent to TM.
Halting problem belongs to the TM. The language in which halting problem belongs is recursively enumerable i.e. RE. In this TM can’t tell in finite time the word is rejected or not. Although it can tell in finite time that the given word is accepted or not. Although REC can tell in finite time and comes into halt about both i.e.
The statement is always true.
If e_{1} and e_{2} are the RE denoting the languages L_{1 }and L_{2} respectively, then which of the following is wrong?
Choice (c) is wrong since “φ” is a regular. In fact
Which of the following is in P?
PATH, HAMPATH, SAT, 3SAT
SAT and PATH is in P while 3SAT and HAMPATH are NPC.
61 videos7 docs102 tests

Use Code STAYHOME200 and get INR 200 additional OFF

Use Coupon Code 
61 videos7 docs102 tests








