Teaching Haryana (HPSC) Assistant Professor Mock Test 2025 Theory of Computation Recursively Enumerable Sets, Turing Machines and Undecidability Undecidability
Which of the following are undecidable?
P1: The language generated by some CFG contains any words of length less than some given number n.
P2: Let L1 be CFL and L2 be regular, to determine whether L1 and L2 have common elements
P3: Any given CFG is ambiguous or not.
P4: For any given CFG G, to determine whether epsilon belongs to L(G).1
P2 only
2
P1 and P2 only
3
P2 and P3 only
4
P3 only
5
Question Not Attempted