# Checking if Post Correspondence Problem has a Solution

I have the following problem

I think that solution is wrong because x1=b and y1=b3(cube).They do not match,So how is this solution possible?

• Look at what the two sides spell out. LHS: $babbb | b | b | ba = babbbbbba=bab^6a$. RHS: $ba | bbb | bbb | a=babbbbbba=bab^6a$. Sure seems like a legit solution to me. – A.Sh Dec 3 '15 at 12:29

Given a PCP instance P, a match is a nonempty sequence $$i_1, i_2, . . . , i_l$$ of numbers from $\{1, 2, . . . , k\}$ (with repetition) such that
$$t_{i1}. t_{i2}· · · t_i = b_{i1} .b_{i2}· · · b_i$$
$MPCP = \{< P > | P$ is a PCP instance and it has a match which starts with index $1\}$.