UGC NET CSE | December 2019 | Part 2 | Question: 52

Question

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?

• A. Only pair $(A, B)$
• B. Only pair $(C, D)$
• C. Both $(A, B)$ and $(C, D)$
• D. Neither $(A, B)$ nor $(C, D)$

Comments

option A?

---

https://gateoverflow.in/189804/post-corresponds-problem

---

This question should be tagged in $\textbf{TOC}$.

Answer 1

$\underline{\textbf{Answer:}\Rightarrow}\;1)\;\text{Only pair (A, B)}$

$\underline{\textbf{Explanation:}\Rightarrow}$

Let $\mathbf A$ be an alphabet with at least two symbols. The input of the problem consists of two finite lists $\mathrm{\alpha_1,\dots,\alpha_N}$ and $\mathrm{\beta_1,\dots,\beta_N}$ of words over $\mathbf A$.

A solution to this problem is a $\mathbf{\color {magenta} {sequence}}$ of indices $\mathrm{(i_k)_{1\le k\le k}}$ with $\mathrm{K \ge 1}$ and $\mathrm{1\le i_k \le N}$ for all $\mathrm k$, such that

$\alpha_{i_1}\dots \alpha_{i_k} = \beta_{i_1}\dots \beta_{i_k}$

The decision problem then is to decide whether such a solution exist or not.

Source: https://en.wikipedia.org/wiki/Post_correspondence_problem

$\mathbf{ \color {green}{\Large A}}$

A1

A2

A3

A4

001

0011

$\color{magenta}{11}$

$\color{magenta}{101}$

 

$\mathbf{ \color {green}{\Large B}}$

B1

B2

B3

B4

$\color{magenta}{\enclose{circle}{01}}$

$\color{magenta}{111}$

$\color{blue}{\enclose{circle}{111}}$

010

 

$\mathbf{ \color {green}{\Large C}}$

C1

C2

C3

00

001

1000

 

$\mathbf{ \color {green}{\Large D}}$

D1

D2

D3

0

11

011

 

$\therefore \mathbf{A,\;B}$ are in $\textbf{PCP}$ because:

$\mathbf{\underset{\enclose{circle}{A_3=11,A_4 = 101}}{A_3A_4} = \underset{\enclose{circle}{B_3=111,B_1=01}}{B_3B_1} = 11101}$, and $\mathbf{\underset{\enclose{circle}{A_3 = 11, A_4 = 101}}{A_3A_4} = \underset{\enclose{circle}{B_2=111,B_1=01}}{B_2B_1}=11101}$

$\therefore $ Pair $\mathbf{A,\;B}$ have a solution.

$\therefore (1)$ is the right answer.

Comments

By index value I mean suffix value and index order is the suffix order.Here it is matching (3,4,1) that's why it has solution.See in the tutorial's point link that you shared in Ex 1 both side for M,N are equal for the order (2,1,3) hence it is the solution.

Length has been mentioned in the sense if the strings produced by a certain sequence are of different lengths then they are not equal,that's obvious.

Just an example, Let M={b,ab} and N={b,ba} .For this no PCP solution exists although $M_1M_2=N_2N_1$ because here $(1,2) \neq (2,1) $.Thus for PCP the necessary condition is strings should be equal and indices order should be equal as well.

---

Okay, So can you answer this:

What's the solution here?

---

This: https://gateoverflow.in/329230/nta-net-dec-2019-post-correspondence?show=330531#c330531

Answer 2

For me answer is D neither of them have solution, as in case os A and B solution is 3 4 1.But what about 2?  we can repetate dominos as many times as we want but all should be used at at least once.

if not so then even C and D has solution 1 1

correct me if I'm wrong?

http://www.nptelvideos.in/2012/11/theory-of-computation.html