4
$\begingroup$

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?

$\endgroup$
  • 7
    $\begingroup$ Show how to convert this model to a finite state machine. $\endgroup$ – Dave Clarke May 10 '12 at 20:23
  • $\begingroup$ A (right-linear) grammar works as well. $\endgroup$ – Raphael May 14 '12 at 14:57
  • $\begingroup$ 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. $\endgroup$ – Raphael May 14 '12 at 14:58
  • $\begingroup$ I know that this is correct because I was requested to prove it.. $\endgroup$ – Jozef May 14 '12 at 16:37
8
$\begingroup$

Hint -- You need to show that your TM has the same power as a finite-state automaton (as the commenter Dave Clarke said), that is, given such a TM, construct a FSA that accepts the same language.

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.

$\endgroup$
7
$\begingroup$

The only difference between a finite automaton and a Turing machine is the tape. The tape provides memory ability. If you can go only on one side, then you simply can't read what you have written.

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).

Note that this is still true if you can only read the cells that are at a bounded distance from the visited cell the most on the right because you have still a bounded memory. Also, the number of tapes and whether you read from a tape or a "standard input" like a DFA does not matter.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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