Register

Recent questions tagged turing-machine

5 votes
3 answers
481
TM Decidablity
Why this statement Turing Machine accepts the null string epsilon ? is not Decidable ? explain with an example.
Why this statement Turing Machine accepts the null string epsilon ? is not Decidable ? explain with an example.
User Avatar
0 votes
2 answers
482
TM Decidablity
Is it decidable whether a given Turing machine accepts a CFL? give some facts or exp to prove your answer .
Is it decidable whether a given Turing machine accepts a CFL? give some facts or exp to prove your answer .
User Avatar
3 votes
1 answer
483
ISI2012-PCB-CS-3
Design a Turing machine that recognizes the unary language consisting of all strings of 0’s whose length is a power of 2, i.e., $L = \{0^{2n} \mid n \geq 0\}$
Design a Turing machine that recognizes the unary language consisting of all strings of 0’s whose length is a power of 2, i.e., $L = \{0^{2n} \mid n \geq 0\}$
User Avatar
4 votes
2 answers
489
TM
Consider the following turning machine (where,,$\$ $ is represent accept the string). If the string is $01010$ then what will be the output? $10100$ $10101$ $10110$ $10011$
Consider the following turning machine (where,,$\$ $ is represent accept the string).If the string is $01010$ then what will be the output?$10100$$10101$$10110$$10011$
User Avatar
4 votes
1 answer
490
Number of symbols necessary to simulate a TM
The number of symbols necessary to simulate a TM with $m$ symbols and $n$ states is ? $m+n$ $8mn+4m$ $mn$ $4mn+m$
The number of symbols necessary to simulate a TM with $m$ symbols and $n$ states is ?$m+n$$8mn+4m$$mn$$4mn+m$
User Avatar
2 votes
1 answer
492
ISRO2014-59
Which of the following is FALSE with respect to possible outcomes of executing a Turing Machine over a given input? it may halt and accept the input it may halt by changing the input it may halt and reject the input it may never halt
Which of the following is FALSE with respect to possible outcomes of executing a Turing Machine over a given input?it may halt and accept the inputit may halt by changing...
User Avatar
0 votes
1 answer
493
Relationship between Problems and Languages
Is there a one to one correspondence between problems and languages? we interchangeably use these while discussing decidabilility and turing machines
Is there a one to one correspondence between problems and languages? we interchangeably use these while discussing decidabilility and turing machines
User Avatar
17 votes
2 answers
502
L(M) = Σ*
$L= \{\langle M \rangle\mid L(M) = \Sigma^*\} $ A. $L$ is RE but $L'$ is not RE B. Both $L$ and $L'$ are RE C. $L$ is not RE but $L'$ is RE D. Both $L$ and $L'$ are not RE
$L= \{\langle M \rangle\mid L(M) = \Sigma^*\} $A. $L$ is RE but $L'$ is not REB. Both $L$ and $L'$ are REC. $L$ is not RE but $L'$ is RED. Both $L$ and $L'$ are not RE...
User Avatar
17 votes
4 answers
503
L(M) is infinite
$L= \{\langle M\rangle \mid L(M)\text{ is infinite}\}$ $L$ is RE but $L'$ is not RE Both $L$ and $L'$ are RE $L$ is not RE but $L'$ is RE Both $L$ and $L'$ are not RE
$L= \{\langle M\rangle \mid L(M)\text{ is infinite}\}$$L$ is RE but $L'$ is not REBoth $L$ and $L'$ are RE$L$ is not RE but $L'$ is REBoth $L$ and $L'$ are not RE
User Avatar
Page: