Proving that there is no solution to the PCP problem using induction

Question

I'm studying for the Algorithms and Computability course. I have encountered a problem that I cannot solve and cannot find any materials to help me solve it. It's the following PCP problem:

We have two sets:

A = (b, a, ca, bac)

B = (ca, ab, a, c).

The task is to find a solution to the given PCP problem or prove that there is none. I know that there will be no solutions, as after choosing elements of the sets with the following indices: 2, 1, 3, 2, 2, 1, 2... we'll end up in a situation where the string formed using set B will always be longer than the first one. Our lecturer wants us to prove it using induction, but unfortunately, I have no clue how to do that. I tried two times on exams and failed every time.

Could anybody show me, what is the correct way to form such a proof or link me to some source that shows that? I will be very grateful.

Answer 1

There is no solution.

Proof by induction

Here is one-line summary: the bottom string is always longer than the top string by a string in the form $(abca\mid abcaaa\mid abcaaab)^+$.

---

Suppose we try to construct a solution by adding dominos one by one, keeping the string on the top row (the top string) and the strong on the bottom row (the bottom string) consistent all the time. "Consistent" means either the top string is a prefix of the bottom string or the bottom string is a prefix of the top string.

Initially both strings are empty. Then, however far we may try, as you have noticed, the bottom string is always longer than the top string.

However, we cannot prove that simple statement by straightforward induction since, when considered as the induction hypothesis, it is too weak to support the induction step.

---

Let us observe the overhang, the extra part of the bottom string. It changes as follows: $b\to ca \to a\to ab\to bab\to abca\to abcaa\to\cdots$

Continuing, we find the overhang grows as follow: $$\begin{aligned} &\to^*\underline{abca}\\ &\to^*\underline{abcaa}\\ &\to^*\underline{abcaaab}\\ &\to^*\underline{abcaaab}\,\underline{abca}\\ &\to^*\underline{abca}\,\underline{abcaaab}\,\underline{abca}\\ &\to^*\underline{abcaaab}\,\underline{abca} \,\underline{abcaa}\\ &\to^*\cdots \end{aligned}$$ where $o_1\to^* o_2$ means overhang $o_1$ is transformed to overhang $o_2$ in several steps without ever being empty.

---

Claim (decomposition of the overhang): The overhang is $abca$ when there are 6 dominos. Suppose the overhang is in the form $(abca\mid abcaa\mid abcaaab)^+$. Then it will be transformed to the same form when $3$, $4$ or $6$ dominos are added.
Proof: In the following $W$ stands for some string. The overhang is transformed by the following rules.

• If it is $aW$, the next domino can be and can only be $\begin{bmatrix}a\\ ab\end{bmatrix}$.
  The new overhang will be $Wab$.
• If it is $caW$, the next domino can be and can only be $\begin{bmatrix}ca\\ a\end{bmatrix}$.
  The new overhang will be $Wa$.
• If it is $bW$, where $W$ does not start with $ac$, the next domino can be and can only be $\begin{bmatrix}b\\ ca\end{bmatrix}$.
  The new overhang will be $Wab$.

Hence, we can verify that

• if the overhang is $\underline{abca}W$, then it will become $W\underline{abcaa}$ when $3$ dominos are added.
• if the overhang is $\underline{abcaa}W$, then it will become $W\underline{abcaaab}$ when $4$ dominos are added.
• if the overhang is $\underline{abcaaab}W$, then it will become $W\underline{abcaaab}\,\underline{abca}$ when $6$ dominos are added.

---

With the claim, it is straightforward to use induction to show that the overhang is never empty. That means the bottom string is always longer than the top string. There is no solution to the PCP problem.

Proof by counting

Let us call $\begin{bmatrix}b\\ ca\end{bmatrix},$ $\begin{bmatrix}a\\ ab\end{bmatrix},$ $\begin{bmatrix}ca\\ a\end{bmatrix},$ $\begin{bmatrix}bac\\ c\end{bmatrix}$ type 1, 2, 3, 4 respectively.

Lemma, more type-3 than type-4: Suppose the list of $n$ dominos $d_1, d_2, \cdots, d_n$, $n\ge3$ is a solution. Then there are more type-3 dominos than type-4 dominos in the list.
Proof: The first 3 dominos in the list must be $$\begin{bmatrix}a\\ ab\end{bmatrix} \begin{bmatrix}b\\ ca\end{bmatrix} \begin{bmatrix}ca\\ a\end{bmatrix},$$

where the third domino is $\begin{bmatrix}ca\\ a\end{bmatrix}$ but there is no $\begin{bmatrix}bac\\ c\end{bmatrix}$.

Suppose $d_i$ is type-4. It presents a substring $bac$ on the top row. Since the given list is a solution, it corresponds to a substring $bac$ on the bottom row.

Consider that substring $bac$ on the bottom row. The letter $a$ in the middle is neither preceded by $c$ nor followed by $b$. Hence it can only be brought by some $d_{x(i)}$ of type-3, $1\le x(i)\le n$. $d_i\mapsto d_{x(i)}$ is a correspondence from type-4 dominos to type-3 dominos in the list. Note that a different $d_i$ must be mapped to a different $d_{x(i)}$. Moreover, the third domino, which is type-3 is not mapped to by any type-4 domino.

---

Claim: There is no solution to this PCP problem.
Proof. Suppose there is a solution. Let $\#1, \#2, \#3, \#4$ be the number of type-1,2,3,4 dominos in the solution. The number of $a$s on the top row and on the bottom row are $\#2+\#3+\#4$ and $\#1 +\#2+\#3$ respectively. The number of $c$s on the top row and the bottom row are $\#3+\#4$ and $\#1+\#4$ respectively. So we have $$\begin{aligned} \#2+\#3+\#4 &= \#1+\#2+\#3,\\ \#3+\#4 &= \#1+\#4, \end{aligned}$$ which implies $\#3=\#4$.

On the other hand, there must be at least $3$ dominos in the solution. The lemma says $\#3>\#4$. This contradiction means we do not have a solution.

Answer 2

added. See the answer by John L. for a formalization of my ideas here.

Your observation is correct. The second string is always longer than the first. Now you have to use induction to actually prove that intuition. This can be done by observing some kind of regularity in how those strings look.

For me it is helpful not to focus on the specific pair of strings, but on the overhang. In constructing the pair of strings that form a solution of PCP at any point one of the strings is longer than the other. The prefixes where both strings match can be forgotten, they are no longer relevant.

The regularity I observe is that the second string is always longer (like you said) and always consists of strings in $\{a,b,ca\}^*$.

The induction-proof has to check the basis (at some point this is true) and the induction step (once this is true it will also be true in the next step). The basis you can do yourself.

The induction is in the following style. The overhang on the second component is $a{\cdot}w$ or $b{\cdot}w$ or $ca{\cdot}w$ for some $\{a,b,ca\}^*$ (the induction assumption). If it is $a{\cdot}w$ we must use rule (2) and the new overhang equals $w{\cdot}ab$, which is the form we need in the next step. Similarly the other two cases. In this way we see that we never can loose the overhang as it never becomes empty.

Somehow we should also verify that the overhang never starts with $bac$, so we cannot apply rule (4). I did not consider that here, but it should be part of the inductive property.