Let 𝐴 = {001,0011,11,101} and 𝐵 = {01,111,111,010}. Similarly, let 𝐶 =…

Solution:

Show that the first pair (A,B) has a post-correspondence solution, and the second pair (C,D) does not.

For the pair A = {001, 0011, 11, 101} and B = {01, 111, 111, 010}:

• Take the tile with left = 11 and right = 111 (third tile), then the tile with left = 101 and right = 010 (fourth tile), then the tile with left = 001 and right = 01 (first tile).

• Left concatenation: 11 · 101 · 001 = 11101001

• Right concatenation: 111 · 010 · 01 = 11101001

Since the left and right concatenations are equal, this gives a valid post-correspondence solution for the first pair.

For the pair C = {00, 001, 1000} and D = {0, 11, 011}:

• The lengths of corresponding tiles are: for C = 2, 3, 4 and for D = 1, 2, 3. Each tile in C is exactly one symbol longer than its counterpart in D.

• Therefore any concatenation of chosen tiles from C will be strictly longer than the corresponding concatenation from D by exactly the number of tiles chosen. The total lengths can never be equal, so no post-correspondence solution exists for this pair.

Conclusion: Only the first pair (A with B) has a post-correspondence solution; the second pair (C with D) does not.