To let $ A = {a, b } $ be an alphabet.

$ P = A ^ * times A ^ * $

An instance of the PCP is a non-empty list $ D = (d_1, d_2, …, d_n) in P ^ n $ of couples of words.

To a PCP instance $ D in P ^ n $ an index sequence $ (i_1, i_2, …, i_m) in {1, …, n } ^ m, m in mathbb {N ^ +}, $ is a solution for D if it has the following property:

to the $ (t, b) = d_ {i_1} diamond d_ {i_2} diamond … diamond d_ {i_m}: t = b $

**d)** Now: $ d_1 = (ab, a), d_2 = (ab, ba), d_3 = (ba, b). $ Explain why this PCP instance has no solution.

My Answer: The first part of the pair always has two letters, while the second part has only one letter except a couple. This means that the first part always gets bigger than the second, unless you just use it $ d_2 $ since both the first and the second part each have two letters. But you can not do it $ d_2 $ since the initial letters do not match, you would already have to start with $ d_1 $ or $ d_3 $ which means that the first part becomes much larger than the second part. So you would never come to a solution.

Is there a more formal way to answer the question?

**e)** What are the possibilities for the total number of solutions for a random PCP instance?

My Answer: I've tried to think about the different number of letters every Domino has for each part. But it does not seem right.

Can you give me an indication of how to find out if and how many solutions exist?