patternMinor
Right moving turing machines and FSA's
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)$?
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.
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.