HiveBrain v1.2.0
Get Started
← Back to all entries
patternMinor

Right moving turing machines and FSA's

Submitted by: @import:stackexchange-cs··
0
Viewed 0 times
andmovingmachinesturingfsaright

Problem

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

Solution

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.

Context

StackExchange Computer Science Q#78124, answer score: 3

Revisions (0)

No revisions yet.