Book PDF: https://vishub.org/officedocs/13770.pdf Pg 253 of book enter image description here

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.

  • $\begingroup$ 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. $\endgroup$
    – D.W.
    Apr 10 at 18:11
  • $\begingroup$ Also, if you are able, linking to a freely available PDF of the source of the quoted material is helpful. Thank you! $\endgroup$
    – D.W.
    Apr 10 at 18:12
  • $\begingroup$ Got it! Will take care from the next time. $\endgroup$ Apr 11 at 6:21
  • $\begingroup$ Next time is helpful, and it would be even better if you could edit this question to improve it, too. $\endgroup$
    – D.W.
    Apr 11 at 17:03

1 Answer 1


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.

  • 1
    $\begingroup$ Aren't turing machines always deterministic? In the sense that given the position of the tape head, and given the state that we are in, there exists a unique transition. At least this is how Kozen defines it. $\endgroup$ Apr 10 at 2:19
  • 2
    $\begingroup$ @PranksterSabeleye they are of. (The most famous case would be in the NP of the P vs NP problem; P is the problems solvable by a regular Turing machine in polynomial time, and NP the problems solvable by a nondeterministic Turing machine in polynomial time.) $\endgroup$
    – Invariance
    Apr 10 at 3:52
  • $\begingroup$ In Lecture 28 Kozen describes the "standard off-the-shelf model" (his words) which is deterministics single tape. In Lecture 30 we learn about Equivalent models (multitape, two-way infinite, two stacks, counters, enumeration). The notion of nondeterminism is only mentioned in the Historical Notes. I did not see a formal introduction of nondeterministic TM's. Curiously in Lecture 36 other models are described, and it is stated that TM's can simulate Type 0 grammars by applying "productions nondeterministically". Also nondeterministic(!) linear bounded automata are introduced as special TM's. $\endgroup$ Apr 10 at 5:13
  • $\begingroup$ So, Kozen seems to avoid nondeterministic TM's and does not mention the P vs NP problem. On browsing I noted his Miscellaneous Excercises 103: "A nondeterministics Turing machine is one with a multiple-valued transition relation. Give a formal definition of these machines. Argue that every nondeterministic TM can be simulated by a deterministics TM". In conclusion: you are right. That is how Kozen defines it. My answer above assumes nondeterminism in an essential way. I have no alternative. $\endgroup$ Apr 10 at 5:22

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.