# Is matching pairs sufficient?

Book PDF: https://vishub.org/officedocs/13770.pdf Pg 253 of book

This is a snapshot from Dexter C. Kozen - Automata and Computability, Lecture-35, Undecidable problems about CFLs. My question here is that, why should we check triples (3-element substrings)? Why not check if all pairs (2-element substrings match)? I think that pairs (2-element substrings) is a condition sufficient and necessary for deriving $$\beta$$ from $$\alpha$$ in one step. However, I am having trouble finding a counter-example. I have some idea on how to prove the claim for triples (induct on the length of $$\alpha$$ and $$\beta$$), but I fail to see why a similar proof would fail for pairs. Is matching pairs a weaker, equal, or stronger condition than matching triples? Help would be appreciated.

Edit 1: In consideration of one of the answers, I think I should mention that here the TM is considered to be deterministic, that is, given the position of the head and the state that the TM is in, there's a unique transition. Or at least this is how I interpreted it from Kozen. Please correct me if I'm wrong.

According to the idea given by the answer, they want to introduce a blank to the left and right of the head to make it work, but that seems to be possible iff non-determinism is allowed.

• Don't use images as main content of your post. This makes your question impossible to search and inaccessible to the visually impaired; we don't like that. Please transcribe text and mathematics. You can use LaTeX.
– D.W.
Apr 10 at 18:11
• Also, if you are able, linking to a freely available PDF of the source of the quoted material is helpful. Thank you!
– D.W.
Apr 10 at 18:12
• Got it! Will take care from the next time. Apr 11 at 6:21
• Next time is helpful, and it would be even better if you could edit this question to improve it, too.
– D.W.
Apr 11 at 17:03

I assume that the Turing machine $$M$$ is allowed to be nondeterministic. In that case we need three positions.
Consider the possibility that $$M$$ on a certain configuration may move either left or right. Then it is possible to simulate both moves at the same time if we only check neigbouring pairs. The two next states have a blank in between. If we check triples then we see that one of the triples contains two states, and we can disallow that.