Aspire's Library
Study Stuff for MCA Examinations - NIMCET
Previous Year Question (PYQs)
Which of the following problems is/are decidable problem(s) on Turing machine $M$?
$(a)$ $G$ is a CFG with $L(G)=\phi$
$(b)$ There exist two TMs $M_1$ and $M_2$ such that $L(M)\subseteq L(M_1)\cup L(M_2)$
$(c)$ $M$ is a TM that accepts $\omega$ using at most $2^{|\omega|}$ cells of tape
Solution
Statement $(a)$ is decidable because emptiness of a context-free grammar is decidable.
Statement $(b)$ is also decidable in this form, because recursively enumerable languages are closed under union, and the condition can be satisfied by suitable Turing machines.
Statement $(c)$ is decidable because the tape usage is bounded by $2^{|\omega|}$. With bounded tape, the number of configurations becomes finite, so we can decide whether $M$ accepts $\omega$ within this bound.
Therefore, all three statements are decidable.
Online Test Series, Information About Examination,
Syllabus, Notification
and More.
View More
Online Test Series, Information About Examination,
Syllabus, Notification
and More.
View More
