1 votes 1 votes Among II and III. Which one is decidable ? Please explain in detail. Theory of Computation made-easy-test-series theory-of-computation decidability + – Shamim Ahmed asked Jan 4, 2019 • edited Mar 4, 2019 by Rishi yadav Shamim Ahmed 438 views answer comment Share Follow See all 2 Comments See all 2 2 Comments reply shreyansh jain commented Jan 4, 2019 reply Follow Share 2. Decidable 3. Undecidable 0 votes 0 votes rish1602 commented Jun 24, 2021 reply Follow Share decidable decidable undecidable 0 votes 0 votes Please log in or register to add a comment.
0 votes 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. shreyansh jain answered Jan 4, 2019 shreyansh jain comment Share Follow See all 0 reply Please log in or register to add a comment.
