menu
search
Log In
Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true

Subjects

Network Sites

 GO Mechanical
 GO Electrical
 GO Electronics
 GO Civil
 CSE Doubts

MadeEasy Test Series: Theory Of Computation - Decidability

0 votes
131 views

Among II and III. Which one is decidable ? Please explain in detail.

in Theory of Computation
edited by 131 views
0
2. Decidable

3. Undecidable

1 Answer

0 votes
1. Decidable, membership problem for all language except RE is decidable

2. Decidable, run TM on all strings of length atmost k for k steps and accept if TM accepts at least one of the strings.

3. Undecidable, can be reduced to state entry problem.
← Prev. Next β†’
← Prev. Qn. in Sub. Next Qn. in Sub. β†’

Related questions

2 votes
0 answers
1
101 views
MadeEasy Test Series 2018: Theory of Computation - Decidability
Consider the following statements: S1 : Let L be language, reversal of language L cannot contain any string present in β€˜L’ except β€˜βˆˆβ€™. S2 : Concatenation of two different language cannot be commutative until atleast one of them is β€˜Ξ¦β€™ or β€˜βˆˆβ€™. Which of the following is correct?
Consider the following statements: S1 : Let L be language, reversal of language L cannot contain any string present in β€˜L’ except β€˜βˆˆβ€™. S2 : Concatenation of two different language cannot be commutative until atleast one of them is β€˜Ξ¦β€™ or β€˜βˆˆβ€™. Which of the following is correct?
asked Jan 17, 2018 in Theory of Computation Sukhdip Singh 101 views
0 votes
2 answers
3
210 views
MadeEasy Test Series: Theory Of Computation - Decidability
L= {(M)| M is a TM and there exists an input w, |w| < 100, on which M halts}. Is L decidable? Please explain.
L= {(M)| M is a TM and there exists an input w, |w| < 100, on which M halts}. Is L decidable? Please explain.
asked Dec 8, 2016 in Theory of Computation agoh 210 views
3 votes
1 answer
4
463 views
MadeEasy Test Series: Theory Of Computation - Decidability
Consider the following languages A={<M>|M is a TM and |L(M)| >= 3} B={<M>|M is a TM that accepts some string} Which of the following is correct? (a.) A is decidable, B is partially decidable (b.) A is ... decidable (c.) Both A and B are decidable (d.) Both A and B are partially decidable Answer given : (d.) But how?
Consider the following languages A={<M>|M is a TM and |L(M)| >= 3} B={<M>|M is a TM that accepts some string} Which of the following is correct? (a.) A is decidable, B is partially decidable (b.) A is partially decidable, B is decidable (c.) Both A and B are decidable (d.) Both A and B are partially decidable Answer given : (d.) But how?
asked Jan 19, 2016 in Theory of Computation Utk 463 views
Dark theme
Muffin by HΓ©lio Chun
Thanks to Q2A
...