Teaching UGC NET Mock Test Series 2025 (Paper 1 & 2) Theory of Computation Recursively Enumerable Sets, Turing Machines and Undecidability Undecidability
Let A = {001, 0011, 11, 101} and B = {01, 111, 111, 010}. Similarly, let C = {00, 001, 1000} and D = {0, 11, 011}.
Which of the following pairs have a post-correspondence solution?1
Only pair (A, B)
2
Only pair (C, D)
3
Both (A, B) and (C, D)
4
Neither (A, B) nor (C, D)