Teaching UGC NET Mock Test Series 2025 (Paper 1 & 2) Theory of Computation Recursively Enumerable Sets, Turing Machines and Undecidability Undecidability
Consider the following set of statements:
S1: Given a context-free language, there is a Turing machine which will always halt in the finite amount of time and give answer whether language is ambiguous or not.
S2: Given a CFG and input alphabet, whether CFG will generate all possible strings of input alphabet (∑*) is undecidable.
S3: Consider three decision problems P1, P2 and P3. It is known that P1 is decidable and P2 is undecidable. P3 is undecidable if P2 is reducible to P3.
Which of the given statements is true?
1
Both S1 and S2
2
Both S2 and S3
3
Only S1
4
Both S1 and S3