UGC NET Computer Science December 2019 | Question 102

Question 102

---

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. 1. Only pair (A, B)
2. 2. Only pair (C, D)
3. 3. Both (A, B) and (C, D)
4. 4. Neither (A, B) nor (C, D)

Answer : 1. Only pair (A, B)

Question 102 Explanation

Before solving this question, let understand what is PCP problem.
The Post Correspondence Problem is to determine whether a collection of dominos has a match.

Given the following two lists, M and N of non-empty strings over ∑

M = (x₁, x₂, x₃,………, x_n)

N = (y₁, y₂, y₃,………, y_n)

We can say that there is a Post Correspondence Solution, if for some i₁,i₂,..... i_k, where 1 ≤ i_j ≤ n, the condition x_i1 …….x_ik = y_i1 …….y_ik satisfies.

Given data is :
A

A1	A2	A3	A4
001	0011	11	101

B

B1	B2	B3	B4
01	111	111	010

C

C1	C2	C3
00	001	1000

D

D1	D2	D3
0	11	011

Now, A convenient way to view an instance of a Post correspondence problem is as a collection of blocks of the form

Ai

Bi

there being an unlimited supply of each type of block. Thus the given example is viewed as

A1	A2	A3	A4
001	0011	11	101
B1	B2	B3	B4
01	111	111	010

A, B have a PCP solution because
A₃A₄A₁ = 11 . 101 . 001 = 11101001 = 111. 010 . 01 = B₂B₁B₁

Furthermore, since (3, 4, 1) is a solution, so are all of its "repetitions", such as (3, 4, 1, 3, 4, 1), etc.; that is, when a solution exists, there are infinitely many solutions of this repetitive kind.

So, option 1 is correct answer

Reference : Post correspondence problem example

Previous	Next
UGC NET CS December 2019 - Question 101	UGC NET CS December 2019 - Question 103