# Right moving turing machines and FSA's

I stumbled upon the following post while learning about turing machines:

Right moving turing machine

I kind of understand the intuition behind why a TM that only moves to the right works like a FSA but I can't think of a general way to create a let's say DFA (or NFA, doesn't really matter) which accepts the same language as a given right moving TM.

So my question would be:

Given an only right moving TM $M$, what would be a general method for constructing a DFA $D$ such that $L(M) = L(D)$?

Alternatively, given an only right moving TM $M$, how to construct a NFA $N$ such that $L(M) = L(N)$?

• A Turing machine that only moves to the right is essentially a DFA. A non-deterministic Turing machine that only moves to the right is essentially an NFA. In order to say anything more, you will need to formally define your model of Turing machine that only moves to the right. – Yuval Filmus Jul 20 '17 at 10:20

Given a TM move rule $\delta(q, x)=(p, y, d)$ where, as usual, $q$ is the current state, $x$ is the contents of the current cell, $p$ is the new state, $y$ is the symbol replacing $x$ in the current cell, and $d$ is the direction to move the head. Since the machine can only move right, it is immaterial what gets overwritten on the current cell and since $d$ is always move right, we can ignore both of these, leaving us with moves of the form $\delta(q, x)=(p)$, i.e., the moves for a FA.