Post Correspondence Problem

Input

Alphabet $A$.

Two tuples $s$ and $t$ of equal length containing strings over $A$.

For bounded problem: $k \in \mathbb{N}$.

Output

Decision version

True or False.

Non-decision version

Indices: $\{0, 1, \ldots, |s| \}$.

Any tuple of indices $(i_0, i_1, \ldots, i_n)$ so that

$ \oplus_{j=0}^n \, s[i_j] = \oplus_{j=0}^n \, t[i_j] $

where $\oplus$ means concatenate and

$s[i_j]$ means the element of $s$ at index $i_j$.

So, $1001 \oplus 00$ is $100100$.

If no such tuple of indices exists, return False.

Algorithm

For the bounded problem.

Exercise

Write a Python function called corresponds. It should take two lists of the same length containing strings over the same alphabet. It shouls also take a positive integer k. It should return any list (of length at most k) of indices of the two lists such that it solves the Post Correspondence Problem. If there is none, the function should return False.