What is the point of finite automata?

Question

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?

Answer 1

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?

Answer 2

We bother with finite automata precisely because they don't do exactly the same thing as Turing machines. As you say in your second sentence, Turing machines accept the same languages and more (my emphasis).

Turing machines are much more powerful. Of course, in many ways, that's a good thing. Why would you ever want to use a less powerful model of computation? Well, in many circumstances, that less powerful model is good enough for what you need. Using the less powerful model means you have certain guarantees. For example, a finite automaton operates in linear time, whereas a Turing machine might take any amount of time or even not terminate for some inputs. This also often makes it easier to prove things about automata than Turing machines.

Automata are also good in teaching terms: you can get students used to the simpler model before moving on to more complex machines such as pushdown automata and Turing machines. Indeed, it's natural to view PDAs as automata with stacks, and Turing machines as automata with tapes.

There are also correspondences with automata and other systems, which are evidence that automata aren't some arbitrary thing. You probably know they're equivalent to regular expressions; they also define exactly the same class of languages as monadic second-order logic.

Answer 3

I will try not to repeat what was well said in previous answers, but I think it may be worth underscoring some points.

When you take a very general problem, it may have no algorithmic solution, it may be undecidable. That means there is no finite way of describing a systematic way of solving the problem in all cases. Typically, questions that you ask about a Turing Machine (TM) are often undecidable (see Rice theorem).

When you restrict your problem to a subclass, to TM with specific properties, then you can find a solution. And if you restrict enough, you may even be able to find efficient solutions. This is actually a restatement of jkff's answer that "you can do less, but you can say more". But not exactly, by being able to say more, there are things that you can do on specific problems that you would not be abled to do otherwise.

Since many programming languages are Turing complete, many things that you would like to know about programs are undecidable. This is often a problem as you need the information to do such things as program optimization. You are blocked by the generality of the problem. But sometimes, though undecidable in general, a question may be decidable for a large subset of the general problem. It may even be that the undecidability results from a combination of features of the language that are know to be seldom used. So studying a restricted class of solution may become decidable and yield useful results.

Another point is that a lot of problems map naturally on regular languages or FSA. Then, when you have to deal with such problems, why make things complicated with a too powerful TM, when a simple FSA will do the job. Do you really need a truck to go to the drugstore buy a pack of chewing gum. And FSA are useful and sufficient for many purposes, both practical and theoretical.

Another way to put it is that a FSA is just a TM with specific properties: it never write, and it scans the non-blank part of the tape only once from left to right (actually, all that matters is that it does not write). So whatever is said about FSA is actually simply said about TM having specific properties.

But that is something we do all the time. For example you can study the properties of equilateral triangles. When you do that, you do not keep repeating, a triangle with thre equal sides. You make a definition: an equilateral triangle is a triangles that has three equal sides, and then you just use the new terminology. Sometimes definition can be more complex, making the convenience undispensable. Well, talking of FSA is the same: a name for a specific kind of TM, so that you can be less verbose when studying it.

Or to be even more mundane. When you say: on a sunny day I do not take my umbrella, think of what the sentence would become if you had to replace sunny and umbrella by their definition or description. Not to mention the other words of the sentence.

Answer 4

A point not made in earlier answers, is that finite automata model real-world computing devices because any device you can really build has only a finite amount of memory.