So there’s following problem, that has been bugging me for the last few days:

A solution of a PCP $ i_{1}.,..,i_{n}$ with the cards $ (x_{1}, y_{1})…(x_{m}, y_{m})$ is considered as k-limited if for all $ j\leq k$ we say that $ \mid\mid x_{i_{1}}.,..,x_{i_{j}}\mid – \mid y_{i_{1}}.,..,y_{i_{j}}\mid\mid \leq k$ .

So after every time we add another card to our sequence, the difference between the upper and lower part of the card should be $ \leq k$ .

Apparently it is decidable for a fixed k, that a PCP-instance has a k-limited solution. We were told that we should try solving this problem with a DFA over the input alphabet {1…m} – where the word $ i_{1}.,..,i_{n}$ will only be accepted if it is k-limited.

Now my problem is that I don’t know how to construct a DFA that can check if a solution is k-limited and a PCP-solution at the same time.