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

What is the point of finite automata?

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

Problem

Why learn finite automata when Turing machines do exactly the same thing? Turing machines accepts the same languages and more so what's the point?

Solution

Turing machines express all computation, so studying turing machines is studying computation in general; theorems that are true about all turing machines are true about all computations. Necessarily, these have to be extremely general and rather vague or weak theorems. If the only thing you know about a computation is that it's implementable using a Turing machine, that's very little knowledge to work with.

Finite automata are a very particular class of computations. Because they are so restricted, you can do less using a finite automaton, but you can say/know more about one. There are tons of very useful theorems that are only true for finite automata but not for arbitrary computations; algorithms and data structures for working specifically with finite automata. E.g., in practical terms, if you compile a regular expression to a finite automaton, you know for sure that it terminates in linear time on every input, you can optimize that automaton, you can think of very efficient ways to write finite-automata evaluators, seek ways to implement incremental evaluation, etc. - none of these problems are solvable or even make sense for "computations in general".

Think of the difference between turing machines and finite automata as the difference between all natural numbers and prime numbers. How would you answer if someone asked you why do we need to study prime numbers, when we already have the concept of natural numbers?

Context

StackExchange Computer Science Q#33413, answer score: 17

Revisions (0)

No revisions yet.