Question 16791 – NTA-UGC-NET 2021 Dec & 2022 June Paper-2
December 2, 2023Question 843 – Computer-Networks
December 3, 2023Question 7717 – Theory-of-Computation
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?
Correct Answer: A
Question 543 Explanation:
Before solving this question you should know what is PCP problem.
The Post Correspondence Problem (PCP), introduced by Emil Post in 1946, is an undecidable decision problem. The PCP problem over an alphabet ∑ is stated as follows −
The Post Correspondence Problem (PCP), introduced by Emil Post in 1946, is an undecidable decision problem. The PCP problem over an alphabet ∑ is stated as follows −
Given the following two lists, M and N of non-empty strings over ∑ −
M = (x1, x2, x3,………, xn)
N = (y1, y2, y3,………, yn)
We can say that there is a Post Correspondence Solution, if for some i1,i2,………… ik, where 1 ≤ ij ≤ n, the condition xi1 …….xik = yi1 …….yik satisfies.
Only pair (A, B)
Only pair (C, D)
Both (A, B) and (C, D)
Neither (A, B) nor (C, D)