Are the instances of PCP solvable?

[mathmari]

Hey!

Are the following instances of post correspondence problem solvable? Find, if possible, various non-periodic solutions or prove the insolubility.

1. $\alpha = (bb, ab, aab)$, $\beta = (abb, a, bba)$
2. $\alpha = (bab, baa, a, aabbb)$, $\beta = (b, a, aba, ababbb)$ For the first one I tried various sequences but I didnt find a common sequence so I suppose that this one is not solvable. Is that correct?

To prove that, we suppose that the problem is solvable.

There exists a $k\in \mathbb{N}$ and a seuquence of indices $i_1, \ldots , i_k\in \{1, 2, 3\}$ with $\alpha_{i_1}\dots \alpha_{i_k}=\beta_{i_1}\dots \beta_{i_k}$.

How can we continue to get a contradiction? Or is the problem solvable? (Wondering) At the second one, the number of "a" in $\alpha$ is not the same as the number of "a" in $\beta$. Would that imply that this problem is also not solvable? (Wondering)

 

[Valkarie]

Yes, that implies that the problem is not solvable. Since the number of "a" in $\alpha$ is not equal to the number of "a" in $\beta$, there cannot be a sequence of indices $i_1, \ldots , i_k\in \{1, 2, 3\}$ with $\alpha_{i_1}\dots \alpha_{i_k}=\beta_{i_1}\dots \beta_{i_k}$.