5
$\begingroup$

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?

$\endgroup$
  • $\begingroup$ The work on finite automata is an important part of theoretical computer science. It is part of a very useful hierarchy to classify computational power of different models. It is a good thing to know even when you might not use it a lot in the future and might forget many of it unless you work more on compiler, programming languages etc.. Nevertheless, the basic knowledge of automata are quite useful in giving you a heuristic about many problems' feasibility, time complexity, etc. When you know it, you will find that your search to many solutions can be guided nicely. $\endgroup$ – InformedA Nov 22 '14 at 23:28
  • 1
    $\begingroup$ What research have you done? Have you checked out several automata theory textbooks to see what they had to say (e.g., in their introduction)? Have you looked at cstheory.stackexchange.com/q/14811 and cstheory.stackexchange.com/q/8539? We expect you to do a significant amount of research before asking and to show us in the question what you've done. When your question is only 2 sentences long, that's often a sign that you should probably do some more research on your own before asking. $\endgroup$ – D.W. Nov 23 '14 at 4:59
  • 6
    $\begingroup$ @D.W. is right. You should read "What is the enlightenment I'm supposed to attain after studying finite automata?". I mean everyone should read the answers given there! $\endgroup$ – Hendrik Jan Nov 23 '14 at 17:42
14
$\begingroup$

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?

$\endgroup$
9
$\begingroup$

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.

$\endgroup$
1
$\begingroup$

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.

$\endgroup$
0
$\begingroup$

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.

$\endgroup$
  • 2
    $\begingroup$ Though it is factually true, I think the point was deliberately not made as it is very misleading. When the number of states, even finite, becomes extremely large, the theory of FSA is much less useful, precisely for practical problems, which you invoque as a justification. $\endgroup$ – babou Nov 24 '14 at 0:02
  • $\begingroup$ I'm having trouble reconciling "factually true" with "very misleading". If you want to explore the limitation of what can be done with a digital circuit (for example) then finite automata are your best mathematical model. This is true and I don't think it is misleading. I certainly don't want to mislead anyone to think, for example, that CFGs should not be used because no digital circuit can recognize them. $\endgroup$ – Theodore Norvell Nov 24 '14 at 1:51
  • 1
    $\begingroup$ If you are thinking of harware circuits of reasonable size, you can probably say that. But you were not explicit about it. The kind of statement you make may be interpreted (and often is) as computers are finite state machines, hence we need nothing more. But, if you take the basic powerset algorithm to build a DFA from a FSA with $n$ states, you consider an automaton that has $2^n$ states. Now, it you take $n=300$, which is not so large, you exceed the number of particles in the universe. $\endgroup$ – babou Nov 24 '14 at 2:10
  • 1
    $\begingroup$ I considered making this point in my answer but it's not really true. You can implement a Turing machine on a standard PC by using USB memory sticks as the tape. Periodically, the Turing machine simulator will prompt the user to insert the next or previous USB stick: as such, the amount of memory available to the Turing machine is unbounded. This is enough since, after any finite number of steps, a Turing machine can only have used a finite number of tape cells. Though I suppose you could argue that the observable universe only contains enough material to build a finite number of USB sticks. $\endgroup$ – David Richerby Nov 24 '14 at 18:43
  • 1
    $\begingroup$ It is really true as you point out in your last sentence. For most practical purposes we can simulate Turing machines in a finite universe in the sense that we can build a machine that either behaves as the Turing Machine would or that quits with a complaint that it has run out of space. On a less philosophical level, it is true of the components out of which we build computer systems. Your standard PC is a finite machine, as are each of those USB sticks, as is the user, even though the composite machine comprising the PC, the user, and an infinite set of USB sticks is not. $\endgroup$ – Theodore Norvell Nov 25 '14 at 18:56

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.