# k-limited solution for PCP

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.