menu
Login
Register
search
Log In
account_circle
Log In
Email or Username
Password
Remember
Log In
Register
I forgot my password
Register
Username
Email
Password
Register
add
Activity
Questions
Unanswered
Tags
Subjects
Users
Ask
Prev
Blogs
New Blog
Exams
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
Recent Posts
Barc Interview Experience 2020- CSE stream
JEST 2021 registrations are open
TIFR GS-2021 Online Application portal
IIT Jodhpur Mtech AI - Interview Expierence (Summer Admission)
Interview experience at IIT Tirupati for MS program winter admission
Subjects
All categories
General Aptitude
(2.1k)
Engineering Mathematics
(8.5k)
Digital Logic
(3k)
Programming and DS
(5.1k)
Algorithms
(4.5k)
Theory of Computation
(6.3k)
Compiler Design
(2.2k)
Operating System
(4.7k)
Databases
(4.3k)
CO and Architecture
(3.5k)
Computer Networks
(4.3k)
Non GATE
(1.2k)
Others
(1.3k)
Admissions
(595)
Exam Queries
(838)
Tier 1 Placement Questions
(16)
Job Queries
(71)
Projects
(19)
Unknown Category
(1.1k)
Recent Blog Comments
OFFTOPIC:- @Arjun sir why are the questions of...
Yep, the problem was the theme π . I can see...
@Ayush I think problem is because of dark theme,...
then only someone from the officials can help...
Nope, it doesn't. I have tried everything.
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.
made-easy-test-series
theory-of-computation
decidability
asked
Jan 4, 2019
in
Theory of Computation
Shamim Ahmed
edited
Mar 4, 2019
by
Rishi yadav
131
views
answer
comment
0
2. Decidable
3. Undecidable
Please
log in
or
register
to add a comment.
Please
log in
or
register
to answer this question.
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.
answered
Jan 4, 2019
shreyansh jain
comment
Please
log in
or
register
to add a comment.
β 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
made-easy-test-series
theory-of-computation
decidability
madeeasy-testseries-2018
3
votes
3
answers
2
829
views
MadeEasy Test Series: Theory Of Computation - Decidability
@arjun sir please help how is it recognizable?
@arjun sir please help how is it recognizable?
asked
Dec 8, 2016
in
Theory of Computation
Anusha Motamarri
829
views
made-easy-test-series
theory-of-computation
decidability
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
made-easy-test-series
theory-of-computation
decidability
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
made-easy-test-series
theory-of-computation
decidability
...