Teaching Haryana (HPSC) Assistant Professor Mock Test 2025 Theory of Computation Recursively Enumerable Sets, Turing Machines and Undecidability Undecidability
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)?1
3 only
2
3 and 4 only
3
1, 2 and 3 only
4
2 and 3 only
5
Question Not Attempted