toc Prep

Undecidability and Rice's Theorem Applications (Variation 9)

Asked by Rahul_Mehta | Textbook Reference: Peter Linz (TOC)

Which of the following problems are **UNDECIDABLE**? Select all that apply. 1. Determining if a given Turing Machine $M$ halts on an empty tape. 2. Determining if the language recognized by a Turing Machine $M$ is empty. 3. Determining if a given DFA $D$ accepts all strings. 4. Determining if the language recognized by a PDA $P$ is regular.

Community Explanations (3)

[Variation 9 Explanation] Let's analyze each problem: 1. **Halts on empty tape:** Undecidable (Halting Problem on blank input). 2. **Language is empty:** Undecidable (Rice's Theorem: Emptiness is non-trivial). 3. **DFA accepts all strings:** Decidable! DFA properties can be checked in $O(V+E)$ time by path exploration. 4. **PDA language is regular:** Undecidable (Non-trivial property of CFLs). Thus, 1, 2, and 4 are undecidable. This corresponds to Option B.

Answered by NileshNama | Agreed by 38 peers | ✓ Selected Solution

[Variation 9 Explanation] ### Alternative Approach / Shortcut Method We can also solve this problem by eliminating incorrect choices or utilizing shortcut relations. For a GATE candidate, speed is as important as accuracy. Let's apply the standard boundary cases: - Let's check with small values of $N$ (e.g. $N=1, 2, 3$). - By substituting these values into our formulas, we can easily see that options matching the base cases are confirmed. This alternative proof validates our selected consensus solution!

Answered by Pradyumna_Rao | Agreed by 9 peers

[Variation 9 Explanation] ### Critical Warnings & Common Student Pitfalls Many students make simple mistakes when solving this type of problem in the exam pressure: 1. **Incorrect base case handling:** Forgetting to handle empty arrays, null pointers, or boundary limits like 0/1 properly. 2. **Off-by-one errors:** Especially in address translation, CIDR masks, or index iterations. 3. **Mismatched units:** Mixing up bits vs bytes, or Hertz vs seconds. Always double-check your calculations step-by-step to avoid losing negative marking on simple questions!