Which of the following is/are undecidable? 1. \(G\) is a CFG. Is \(L(G) =…
20132013
Which of the following is/are undecidable?
1. \(G\) is a CFG. Is \(L(G) = \phi\)?
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)\)?
- A.
3 only
- B.
3 and 4 only
- C.
1, 2 and 3 only
- D.
2 and 3 only
Attempted by 84 students.
Show answer & explanation
Correct answer: D
Answer: The undecidable statements are 2 and 3.
1. Given a CFG G, is L(G) = ∅? — Decidable. You can decide this by computing which nonterminals can generate terminal strings and whether the start symbol is among them (standard reachability/generation algorithm).
2. Given a CFG G, is L(G) = Σ*? — Undecidable. Universality for context-free grammars is a known undecidable problem.
3. Given a Turing machine M, is L(M) regular? — Undecidable. By Rice's theorem, any nontrivial property of the language recognized by a TM (such as being regular) is undecidable.
4. Given a DFA A and an NFA N, is L(A) = L(N)? — Decidable. Convert the NFA to an equivalent DFA, form the symmetric difference of the two DFAs, and check emptiness of that language; emptiness for finite automata is decidable.
Therefore the correct choice is the one that lists statements 2 and 3 as undecidable.
A video solution is available for this question — log in and enroll to watch it.