Aspire's Library

A Place for Latest Exam wise Questions, Videos, Previous Year Papers,
Study Stuff for MCA Examinations - NIMCET

Previous Year Question (PYQs)



 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?





Solution

For pair $(A,B)$:

Take sequence of indices:

$3,4,1$

From $A$ side:

$A_3A_4A_1=11\ 101\ 001=11101001$

From $B$ side:

$B_3B_4B_1=111\ 010\ 01=11101001$

Both strings are equal.

So, pair $(A,B)$ has a PCP solution.

For pair $(C,D)$:

Starting must be with first pair because only it gives matching prefix:

$C_1=00,\ D_1=0$

After this, extra $0$ remains on upper side. Repeating first pair keeps increasing extra zeros, and other pairs do not match the required prefix properly.

So, pair $(C,D)$ has no PCP solution.



Online Test Series,
Information About Examination,
Syllabus, Notification
and More.

Click Here to
View More


Online Test Series,
Information About Examination,
Syllabus, Notification
and More.

Click Here to
View More

Ask Your Question or Put Your Review.

loading...