3
$\begingroup$

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)$?

$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – Yuval Filmus Jul 20 '17 at 10:20
3
$\begingroup$

As Yuval indicated in the comment, a right-moving TM is already essentially a FA. Here's the construction:

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.

The construction above is for a DFA, the one for a NFA is essentially the same.

$\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.