# $L(M) = L$ where $M$ is a $TM$ that moves only to the right side so $L$ is regular

Suppose that $L(M) = L$ where $M$ is a $TM$ that moves only to the right side.

I need to Show that $L$ is regular.

I'd relly like some help, I tried to think of any way to prove it but I didn't reach to any smart conclusion. what is it about the only side right moves and the regularity?

• Show how to convert this model to a finite state machine. May 10 '12 at 20:23
• A (right-linear) grammar works as well.
– Raphael
May 14 '12 at 14:57
• As you still seem to know which answer is correct, may I suggest to take a step back conciously: have you tried finding an example for the opposite statement? That is often helpful.
– Raphael
May 14 '12 at 14:58
• I know that this is correct because I was requested to prove it.. May 14 '12 at 16:37

But since the TM has no memory but the tape, ask yourself what a right-only TM can do with its tape. It should be relatively straightforward to actually construct the parts of the FSA you are looking for. Just go through them -- the states, the input alphabet and most crucially the move function (usually $\delta$) and define them in terms of the parts of the TM you started with. Then you have to show that the two accept the same language, in terms of the definition of "accept" for each, being sure to mention potential looping behavior in the TM.
BTW, this sort of problem is amenable to a pretty convincing "hand-waving" proof that would actually be of a type that is quite acceptable in a research paper. Your course, however, may be expecting a precise proof, using $\delta$ and the other components of the tuples that constitute the TM and FSA.
To formally prove this you build an automaton from your machine $M$. Suppose $A$ is the automaton in $M$. Then your automaton $A'$ will be the same as $A$ with a one-cell memory, because you can still read the cell you are on in $M$. (Number of states of $A'$ = number of states of $M$ $×$ size of the alphabet of the tape).