Show that the single-tape TMs that can not write on the portion of the tape containing the input string recognize only regular languages

Question

Show that the single-tape TMs that can not write on the portion the portion of the tape containing the input string recognize only regular languages.

The first part of the answer in a book said that:

We give a DFA $A$ that is equivalent to TM $M$. Design $A$ in two stages.

1. We arrange the states and transitions of $A$ to simulate $M$ on the read-only input portion of the tape.

2. We assign the accept states of $A$ to correspond to the action of $M$ on the read/write portion of the tapeto the right of the input.

Given below the whole answer (sorry for using pictures but the answer was so long and I do not understand it and I have not enough time to write it):

But I do not understand many points:

1. Why the domain and the codomain of the defined function takes this form? and why only finitely many such functions exist as stated by the last line in the first paragraph?

2. Why the author wrote $F_{\epsilon}$ as in the third paragraph? did he used the idea of epsilon transitions?

3. The last paragraph in the solution I did not understand its idea at all?

Could anyone clarify the above questions for me please?

I saw an answer for the question here Single-tape Turing Machines with write-protected input recognize only Regular Languages but I did not understand it at all.

Answer 1

The general idea is that the TM has only finite memory while being in the input part of the tape. It can do arbitrary computations in the right part of the tape, but it can only observe a finite memory footprint of the input. It starts in the input part (on the left) and it can reenter the input part (from the right) arbitrarily often. But each time it enters the input part, the only thing that matters is the state it has when entering (or the fact that it starts from the left). And the only outcome of processing the (read-only) input part is the state it has when it exits (or the fact that it does not exit because it has accepted or rejected in the meantime).

1. That is already the reason for the domain and codomain. The domain is everything that matters about entering the input part, the codomain is everything that matters about exiting that part. Hence the function completely describes the behaviour of the TM on the input part. In a sense, the function contains everything the TM will ever find out about the word $s$. Both domain and codomain are finite, hence so is the set of functions. Although the definition is about infinitely many words $s$, there will only be a finite number of different functions $F_s$.

2. $F_{\varepsilon}$ is not about $\varepsilon$-transitions. And it does not expand the previous definition. It is just the special case $s=\varepsilon$, that is the case of the empty input word. Or rather, the case of the empty prefix. After all, the paragraph where this appears is all about how $F_s$ can be computed incrementally along with prefixes of $s$.

3. By now we have fully defined the automaton, except for acceptance. And the automaton state fully describes what the TM can do with the word we have read. We have not yet said anything about the part of the TM's computation that happens outside of the input word. The trick is that we do not have to delve into that computation. We just say that the state $F_s$ is accepting if the word $s$ belongs to the TM's language. The paragraph has an explanation of why that is well-defined.

Answer 2

Actually, you don't need to construct the DFA, you just need to show that it exists using the Myhill Nerode theorem.

Here's how: given a machine $M$ that cannot write on its input, suppose the input has a prefix $s$. We can then ask the following questions:

1. If $M$ is in its start state $q_0$ and its tape head points to the first symbol in $s$, does the tape head ever go past $s$, i.e. to the first slot after $s$? If it does, what state will it be in? If it does not (i.e. the head will always stay within $s$) does $M$ eventually accept or not?

2. If $M$ is in some state $q$ and its tape head points to the last symbol in $s$, does the tape head ever go past $s$? If it does, what state? If it does not, does $M$ accept?

Let $G(s)$ be the tuple of answers to the above for any string $s$. The answer to 1. is one component of the tuple, and the answers to 2. (one for each $q$) are the other components. We can make two key observations:

I. The number of possible values of the tuple is finite. This is because the value of each component is either a state $q^\prime$ or "accept" or "reject". Hence, the possible values is just a simple cartesian product.

II. For any two strings $s$ and $t$, if $G(t) = G(s)$, then for any suffix $z$, either $M$ accepts both $sz$ and $tz$, or $M$ accepts neither $sz$ nor $tz$.

Observation II. can intuitively be seen by noticing that for any $s$ and $t$, when the tape is in the portion after the $s$ or $t$, we know that there will be no differences, as long as the same $z$ is chosen as the suffix for both. Additionally, if $G(s) = G(t)$, then we know that the behavior is also identical within the $s$ or $t$, hence it is identical for the two everywhere in the tape.

I. and II. allow us to divide all possible $s$ into a finite number of Myhill-Nerode equivalence classes. Hence, a DFA recognizing the language of $M$ exists.