Write protected input turing machine is a single-tape TM that cannot write on the input portion of the tape. I almost prove that these TMs can only recognize regular languages but i have a problem in one of my steps.

In one step of proof i define a characteristic function $f_w$ such that for any $q \in Q, f_w(q)=q’$ implies that if TM $M$ is at state $q$ just before going back to input portion, the next time that going out from the input portion will change $M$ in satate $q’$ unless we halt inside the input portion.

Now what i need to prove is that for any two string $w_1$ and $w_2$ if for every $q \in Q$ we have the same value for $f_{w_1}(q)$ and $f_{w_2}(q)$ then for every $z \in \Sigma^*$ we have $f_{w_1z}(q)=f_{w_2z}(q)$

It is sensible for me and i have some idea to prove this , one of my idea is that if i can prove for every $f_w(q)$ there is a 2FSA then appending one character to $w$ leads us to a same equivalance class.

Am i in the right path ?



Your Answer

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