patternModerate
What is the relationship between Turing Machines with a finite tape and Finite State Automata?
Viewed 0 times
thefinitewhatwithandautomatabetweentapestatemachines
Problem
I seem to recall from an undergraduate class that for a Turing Machine with a finite tape there will always exist a corresponding Finite State Automata, but I've been unable to find this confirmed anywhere on the internet. Is this actually the case or am I misremembering?
Solution
It depends what you mean by "finite tape". If you bound the length of the tape by some function of the input, then no - you can recognize non-regular languages. For example, consider LBAs.
But if you mean a bounded tape, where the tape has $k$ cells for some fixed $k$, then yes - you indeed get a model which is equivalent to DFAs.
To prove this, consider what information you need to determined the future of a run of a TM: you need the contents of the tape, the location of the head, and the state. If the tape has a constant number of cells, and the alphabet is fixed, then you have a constant number of configurations, which you can encode as states of a finite automaton.
But if you mean a bounded tape, where the tape has $k$ cells for some fixed $k$, then yes - you indeed get a model which is equivalent to DFAs.
To prove this, consider what information you need to determined the future of a run of a TM: you need the contents of the tape, the location of the head, and the state. If the tape has a constant number of cells, and the alphabet is fixed, then you have a constant number of configurations, which you can encode as states of a finite automaton.
Context
StackExchange Computer Science Q#40911, answer score: 15
Revisions (0)
No revisions yet.