Project ForgeTheory of Computation
Grammars, Turing Machines & Decidability
GATE 2013
Hard
Which of the following is/are undecidable?
1. G is a CFG. Is L(G) = Φ? 2. G is a CFG. Is L(G) = Σ*? 3. M is a Turing machine. Is L(M) regular? 4. A is a DFA and N is an NFA. Is L(A) = L(N)?
- A3 only
- B3 and 4 only
- C1, 2 and 3 only
- 2 and 3 only
Explanation
CFG emptiness (1) is decidable via a standard reachability algorithm. CFG universality (2), whether L(G)=Σ*, is undecidable. Whether an arbitrary Turing machine's language is regular (3) is undecidable by Rice's theorem (a non-trivial semantic property of RE languages). DFA-vs-NFA language equivalence (4) is decidable — both can be converted to DFAs and compared. So 2 and 3 are undecidable.
Source: GATE CS 2013 (2013)
This question is part of a 15-day revision cycle — sign in and Project Forge will bring it back the day before you'd forget it.