UGC NET CSE | October 2022 | Part 1 | Question: 2

Question

Consider two lists $\mathrm{A}$ and $\mathrm{B}$ of three strings on $\{0,1\}$
$X$ : 

List A	List B
$1$	$111$
$10111$	$10$
$10$	$0$

$Y$:

List A	List B
$10$	$101$
$011$	$11$
$101$	$011$

Which of the following is true?

• A. Only PCP in $\text{X}$ has solution.,
• B. Only PCP in $\text{Y}$ has solution.,
• C. PCP in both $\mathrm{X}$ and $\mathrm{Y}$ has solution.
• D. PCP neither in $\mathrm{X}$ nor in $\mathrm{Y}$ has solution.,

Answer 1

The goal of PCP is to arrange the input in such a way that the string created by the denominator and the numerator is same. 

X

List A	List B
1	111
10111	10
10	0

$\ start\ with\ 2^{nd} \ row$   

 $\frac{10111}{10}\ there \ is\ remaining\ 111\ in\ numerator\ to\ satisfy\ this\ take\ 1^{st}\ row$

$\frac{10111}{10}\frac{1}{111}$

$\ now \ take\ again\ 1^{st}\ row$

$\frac{10111}{10}\frac{1}{111}\frac{1}{111}\\ $

$\ now \ will\ take\ 3^{rd}\ row$

$\frac{10111}{10}\frac{1}{111}\frac{1}{111}\frac{10}{0}$

$\  X\ has\ a\ solution$

Y

List A	List B
10	101
011	11
101	011

$\ start\ from\ where\ starting\ string\ matches$

$\ so\ start\ with\ 1^{st}\ row$

$\frac{10}{101}\ here\ remaining\ string\ in\ denominator\ is\ 1$

$\ take\ 3^{rd}\ row$

$\frac{10}{101} \frac{101}{011}$

$\ again\ remaining\ string\ in\ denominator\ is\ 1\ and\ it\ will\ be\ infinte$

$\ Y\ has\ no\ solution.$

$\ Answer:\ Only\ PCP\ in\  X\ has\ solution\ and\ PCP\ in\ Y\ has\ no\ solution.$

Comments

$X\ has\ solution\ string\ is\ 2113$