<p>There are many good theoretical reasons to study N/DFAs.  Two that immediately come to mind are:</p>

<ol>
<li><p>Turing machines (we think) capture everything that's computable.  However, we can ask: What parts of a Turing machine are "essential"?  What happens when you limit a Turing machine in various ways? DFAs are a very severe and <em>natural</em> limitation (taking away memory).  PDAs are a less severe limitation, etc.  It's theoretically interesting to see what memory gives you and what happens when you go without it.  It seems a very <em>natural</em> and basic question to me.</p></li>
<li><p>Turing machines need an infinite tape.  Our universe is finite, so in some sense every computing device is a DFA.  Seems like an important, and again natural, topic to study.</p></li>
</ol>

<p>Asking why one should study DFAs is akin to asking why one should learn Godel's <a href="http://en.wikipedia.org/wiki/G%C3%B6del%27s_completeness_theorem">completeness</a> theorem when the real interesting thing is his <a href="http://en.wikipedia.org/wiki/G%C3%B6del%27s_incompleteness_theorems">incompleteness</a> theorem.</p>

<p>The reason they are the first topic in automata theory is because it's natural to build up to more complicated modes from less complicated ones.</p>

CC BY-SA 3.0
2012-12-23T07:05:19.010Z
#1 makes good sense and I think I see the reason. But how would you explain the reason 'going forward' from FAs? Those who know something about ToC can backtrack in retrospect and mull on it. How best to explain the 'why' to students who start learning automata theory and only know FAs? Do we just state we are starting with one bit machines since they are basic - why? How best to answer 'that' why? Would appreciate some light when answering this question for total noobs to ToC :)
PhD
CC BY-SA 3.0
2012-12-23T07:17:57.887Z
The "forward" argument comes from the fact (as Sariel mentioned) that state machines are perhaps the most basic of computing devices. You're in a state: something happens, and then you move to a new state. Note that markov chains (which are very important in machine learning) are just probabilistic FSMs.
Suresh Venkat
CC BY-SA 3.0
2012-12-23T04:23:35.427Z
2012-12-23T05:10:31.560Z
2012-12-23T05:10:31.560Z
Lev Reyzin
<p>To add one more perspective to the rest of the answers: because you can actually do stuff with finite automata, in contrast with Turing machines.</p>

<p>Just about any interesting property of Turing machines are undecidable. On the contrary, with finite automata, just about everything <em>is</em> decidable. Language equality, inclusion, emptiness and universality are all decidable. Combined with that finite automata are closed under just about every operation you can think of, and that these operations are computable, you can do pretty much anything you'd ever want to do with finite automata.</p>

<p>This means that if you can capture something using finite automata, you automatically gain a lot of tools to analyze it. For instance, in software testing, systems and their specifications can be modeled as finite automata. You can then automatically test whether your system correctly implements the specification.</p>

<p>Turing machines and finite automata therefore teach people an interesting and ubiquitous contrast: more descriptive power goes hand in hand with less tractability. Finite automata can't describe much, but we can at least do stuff with them.</p>

CC BY-SA 3.0
2012-12-24T16:44:12.350Z
"...you can actually do stuff with finite automata, in contrast with Turing machines." understand the pt, however a quote that sounds ironic or doesnt make much sense taken out of context...
vzn
CC BY-SA 3.0
2012-12-23T13:21:16.257Z
2012-12-23T13:21:16.257Z
Alex ten Brink
<p>Although it is not really the reason they were originally studied, finite automata and the regular languages they recognize are tractable enough that they have been used as building blocks for more complicated mathematical theories. In this context see particularly <a href="http://en.wikipedia.org/wiki/Automatic_group">automatic groups</a> (groups in which the elements can be represented by strings in a regular language and in which the products of elements by group generators can be computed by finite state transducers) and <a href="http://en.wikipedia.org/wiki/Sofic_subshift#Characterization_and_sofic_subshifts">sofic subshifts</a> (subshifts of a shift space whose forbidden words form a regular language). So there are reasons to study them even if you are interested in pure mathematics rather than computer science.</p>

<p>Finite automata have also been used in the design of algorithms for other kinds of objects. For instance, <a href="http://www.complex-systems.com/pdf/01-6-1.pdf">an algorithm of Culik for testing whether a one-dimensional cellular automaton is reversible</a> involves constructing, modifying, and testing the properties of certain NFAs. And a <a href="http://dl.acm.org/citation.cfm?id=1382439.1382941">1986 FOCS paper by Natarajan</a> showed how to solve a certain problem in the design of mechanical assembly lines by reducing it to a computation about finite automata.</p>

CC BY-SA 3.0
2012-12-23T05:40:57.307Z
2012-12-23T05:40:57.307Z
David Eppstein
<p>You are asking (at least) two different questions: (a) What parts of theory build on finite automata nowadays? (b) Why were finite automata developed in the first place? I think the best way to address the latter is to look at the old papers, such as:</p>

<ul>
<li>Rabin, Scott, <a href="http://www.google.co.uk/search?q=Finite%20automata%20and%20their%20decision%20problems">Finite Automata and Their Decision Problems</a>, 1959</li>
</ul>

<p>Here are the first two paragraphs:</p>

<blockquote>
  <p>Turing machines are widely considered to be the abstract prototype of
  digital computers; workers in the field, however, have felt more and
  more that the notion of a Turing machine is too general to serve as an
  accurate model of actual computers. It is well known that even for
  simple calculations it is impossible to give an <em>a priori</em> upper bound
  on the amount of tape a Turing machine will need for any given
  computation. It is precisely this feature that renders Turing's
  concept unrealistic.</p>
  
  <p>In the last few years the idea of a <em>finite automaton</em> has appeared in
  the literature. These are machines having only a finite number of
  internal states that can be used for memory and computation. The
  restriction on finiteness appears to give a better approximation to
  the idea of a physical machine. Of course, such machines cannot do as
  much as Turing machines, but the advantage of being able to compute an
  arbitrary general recursive function is questionable, since very few
  of these functions come up in practical applications.</p>
</blockquote>

<p>In short, they were developed as a model of real computers, which have finite resources.</p>

CC BY-SA 3.0
2012-12-23T08:57:08.040Z
2012-12-23T08:57:08.040Z
Radu GRIGore
<p>Another reason is that they're relatively <em>practical</em> theoretical models. A Turing machine, apart from the impossibility of the infinite tape, is kind of an awkward fit for what it's like to program a computer (note that this  is not a good analogy to begin with!). PDAs and DFAs however are quite amenable to being models of actual programs in the sense that a PDA/DFA design can often easily be turned into a real program. Compiler design, for example, uses them extensively. So at these sort of connection points between theory and practice, we get a handle on how it all ties together, and what we can and can't do.</p>

CC BY-SA 3.0
2012-12-23T04:57:46.310Z
2012-12-23T04:57:46.310Z
Luke Mathieson
<p>State. you need to learn that one can model the world (for certain problems) as a finite state space, and one can think about computation in this settings. This is a simple insight but extremely useful if you do any programming - you would encounter state again and again and again, and FA give you a way to think about them. I consider this to be a sufficient excuse for teaching a complete class. Of course, state can be deterministic or non-deterministic. Thus DFA and NFA, but you can convert between them, etc.</p>

<p>The second thing to learn is the Halting theorem. Which is related to the Godel incompleteness theorem. (You can not build a machine that can compute everything, and there are mathematical claims that you can neither proof nor disprove, and as such needed to be taken as axioms. That is, we live in a world that has no finite description or real oracles - yey for us!)</p>

<p>Now, I did my undergrad in math, and you get used to the idea that you learn stuff you have no clue why you are learning (group theory, measure theory, set theory, Hilbert spaces, etc, etc, etc [all good stuff, BTW]). There is something to be said about learning how to learn - next time you have to learn some bizarro math (because you need to use it to do something out there in the real world) that looks very strange you take in stride. Specifically, the third thing to learn is mathematical maturity - being able to argue carefully about things, know when proofs are correct or not, write down proofs, etc. If you have it already, this course is easy, and you would not care too much why you are learning it. </p>

<p>Except for these, the course is a complete waste of your time, like everything else. Specifically, you can live a happy life without knowing this stuff. But this is literally true of all knowledge. More or less. For me a course in university is worth its time, if you look on the world differently after learning it. This is definitely one of the courses that changed the way I think about the world. What more can you ask?</p>

CC BY-SA 3.0
2012-12-23T06:12:13.133Z
2012-12-23T06:12:13.133Z
Sariel Har-Peled
<p>Check out the "Living Binary Adder" Game here : <a href="http://courstltc.blogspot.com/2012/12/living-binary-adder-game.html">http://courstltc.blogspot.com/2012/12/living-binary-adder-game.html</a>
I used to present this game to my students in the early chapters about DFA/NFA. It illustrates two important things in Automata Theory:</p>

<ol>
<li>How to transform a mental process into a simple mechanical one</li>
<li>What abstraction really means. Two states, as C and Z states above, can be anything : transistors in a computer, an hydraulic mechanism or two human players !</li>
</ol>

<p>This, sometimes bring the "Aha" moment to my students.</p>

CC BY-SA 3.0
2012-12-24T10:08:51.287Z
2012-12-26T00:35:44.893Z
2012-12-26T00:35:44.893Z
Tarik FDIL
<p>The concept of DFAs is very useful for designing efficient solutions to many types of problems. One example is networking. Every protocol can be implemented as a state machine. Implementing the solution this way makes the code simpler and simpler means a lower defect rate.  It also means that changes to the code are easier and have a lower impact, again having a lower defect rate. </p>

<p>Some people find it difficult to view a network protocol as a state machine but those who can make the jump find it very rewarding in terms of return on effort. </p>

CC BY-SA 3.0
2015-01-06T16:01:00.300Z
Sounds very ingesting but can you explain a little more? it *is* hard to imagine a network protocol as a state machine. thank you.
hkoosha
CC BY-SA 3.0
2012-12-24T14:35:20.547Z
2012-12-26T00:40:31.967Z
2012-12-26T00:40:31.967Z
geohump
<p>Actually, my students sometimes ask precisely this -- after spending a large chunk of the semester on finite automata and finally arriving at Turing machines. Why spend so much time on a weaker formalism when a stronger one is available? So I explain the inherent tradeoff in expressive power vs. analytic complexity. The richer models are typically more difficult to analyze. The DFA vs. TM dichotomy is extreme, as the membership problem is trivial for one and uncomputable for the other. A less extreme example would be DFA vs. PDA. The membership problem for the latter turns out to be efficiently solvable, but the solution is not at all trivial. We see this occurrennce in many branches of math and science: study a simple model to get as complete an understanding as possible, which usually leads to insights into more complex models as well.</p>

CC BY-SA 3.0
2016-01-14T11:00:13.070Z
2016-01-14T11:00:13.070Z
Aryeh
<p>I see several answers calling FM's "lesser" than Turing machines.</p>

<p>A primary focus in the Post-grad class I took lay in their equivalence, not distinctions. For every FSM model we studied, we had to prove their equivalence to Turing Machines. This is done by implementing a Turing Machine in the FSM. IIRC, we also studied some other computing models that cold not implement a TM, but I forget what those were. The point is, if you can implement a TM, you can run any TM program on the model, given a sufficiently large tape analog for the problem being run.</p>

<p>The thrust of the answer to the question was: TM is the basic computability model, but not very practical when it comes to building useful machines. Hence FSM models.</p>

<p>This was brought home viscerally to me when, at around the same time (1984), I discovered the FORTH language. It's execution engine is built on a pure realization of a Dual Stack PDA. Going deeper I fond this same engine under expression compilers</p>

<p>Although, for me, the real impact of FSM was discovering the book "Theory of Finite Automata" by Trakhtenbrot and Korzynski (?) when I was 18, a discovery that essentially gave me my career.</p>

CC BY-SA 3.0
2012-12-27T01:34:35.850Z
I assume though that you did not prove an equivalence between Nondeterministic Finite Automata and Turing Machines. It is this specific object the OP asked about and that the rest of us are calling "lesser".
Vijay D
CC BY-SA 3.0
2012-12-27T01:46:19.033Z
And an FA is not the same as an FSM.
Suresh Venkat
CC BY-SA 3.0
2012-12-26T19:28:38.397Z
2012-12-26T19:28:38.397Z
David
<p>I have personally enjoyed several <em>Aha!</em> moments from studying basic automata theory. NFAs and DFAs form a microcosm for theoretical computer science as a whole. </p>

<ol>
<li><strong>Does Non-determinism Lead to Efficiency?</strong> There are standard examples where the minimal deterministic automaton for a language is exponentially larger than a minimal non-deterministic automaton. Understanding this difference for Turing machines is at the core of (theoretical) computer science. NFAs and DFAs provide the simplest example I know where you can explicitly see the strict gap between determinism and non-determinism.</li>
<li><strong>Computability != Complexity.</strong> NFAs and DFAs both represent regular languages and are equivalent in <em>what</em> they compute. They differ in <em>how</em> they compute. </li>
<li><strong>Machines Refine Languages.</strong> This is a different take on what we compute and how we compute. You can think of computable languages (and functions) as defining an equivalence class of automata. This is a fundamental perspective change in TCS, where we focus not just on the what, but the how of computation and try to choose the right 'how' when designing an algorithm or understand the space of different how's in studying complexity classes.</li>
<li><strong>The Value of Canonical Representation.</strong> DFAs are the quintessential example of a data-structure admitting a canonical representation. Every regular language has a unique, minimal DFA. This means that given a minimal DFA, important operations like language inclusion, complementation, and checking acceptance of a word become trivial. Devising and exploiting canonical representations is a useful trick when developing algorithms.</li>
<li><strong>The Absence of Canonical Representations.</strong> There is no well accepted canonical representation of regular expressions or NFA. So, despite the point above, canonical representations do not always exist. You will see this point in many different areas in computer science. (for example, propositional logic formulae also do not have canonical representations, while ROBDDs do).</li>
<li><strong>The Cost of a Canonical Representation.</strong> You can even understand the difference between NFAs and DFAs as an algorithmic <em>no-free-lunch</em> theorem. If we want to check language inclusion between, or complement an NFA, you can determinize and minimize it and continue from there. However, this "reduction" operation comes at a cost. You will see examples of canonization at a cost in several other areas of computer science.</li>
<li><strong>Infinite != Undecidable.</strong> A common misconception is that problems of an infinitary nature are inherently undecidable. Regular languages contain infinitely many strings and yet have several decidable properties. The theory of regular languages shows you that infinity alone is not the source of undecidability.</li>
<li><strong>Hold Infinity in the Palm of Your Automaton.</strong> You can view a finite automaton purely as a data-structure for representing infinite sets. An ROBDD is a data-structure for representing Boolean functions, which you can understand as representing finite sets. A finite-automaton is a natural, infinitary extension of an ROBDD. </li>
<li><strong>The Humble Processor.</strong> A modern processor has a lot in it, but you can understand it as a finite automaton. Just this realisation made computer architecture and processor design far less intimidating to me. It also shows that, in practice, if you structure and manipulate your states carefully, you can get very far with finite automata.</li>
<li><strong>The Algebraic Perspective.</strong> Regular languages form a syntactic monoid and can be studied from that perspective. More generally, you can in later studies also ask, what is the right algebraic structure corresponding to some computational problem.  </li>
<li><strong>The Combinatorial Perspective.</strong> A finite-automaton is a labelled graph. Checking if a word is accepted reduces to finding a path in a labelled graph. Automata algorithms amount to graph transformations. Understanding the structure of automata for various sub-families of regular languages is an active research area.</li>
<li><strong>The Algebra-Language-Combinatorics love triangle.</strong> The Myhill-Nerode theorem allows you to start with a language and generate an automaton or a syntactic monoid. Mathematically, we obtain a translation between very different types of mathematical objects. It is useful to keep such translations in mind and look for them in other areas of computer science, and to move between them depending on your application.</li>
<li><strong>Mathematics is the Language of Big-Pictures.</strong> Regular languages can be characterised by NFAs (graphs), regular expressions (formal grammar), read-only Turing machines (machine), syntactic monoids (algebra), Kleene algebras (algebra), monadic second-order logic, etc. The more general phenomenon is that important, enduring concepts have many different mathematical characterizations, each of which brings different flavours to our understanding of the idea.</li>
<li><strong>Lemmas for the Working Mathematician.</strong> The Pumping Lemma is a great example of a theoretical tool that you can leverage to solve different problems. Working with Lemmas is good practice for trying to build upon existing results.</li>
<li><strong>Necessary != Sufficient.</strong> The Myhill-Nerode theorem gives you necessary and sufficient conditions for a language to be regular. The Pumping Lemma gives us necessary conditions. Comparing the two and using them in different situations helped me understand the difference between necessary and sufficient conditions in mathematical practice. I also learnt that a <em>reusable</em> necessary and sufficient condition is a luxury. </li>
<li><strong>The Programming Language Perspective.</strong> Regular expressions are a simple and beautiful example of a programming language. In concatenation, you have an analogue of sequential composition and in Kleene star, you have the analogue of iteration. In defining the syntax and semantics of regular expressions, you make a baby step in the direction of programming language theory by seeing inductive definitions and compositional semantics.</li>
<li><strong>The Compiler Perspective.</strong> The translation from a regular expression to a finite automaton is also a simple, theoretical compiler. You can see the difference between parsing, intermediate-code generation, and compiler optimizations, because of the difference in reading a regular expression, generating an automaton, and then minimizing/determinizing the automaton.</li>
<li><strong>The Power of Iteration.</strong> In seeing what you can do in a finite-automaton with a loop and one without, you can appreciate the power of iteration. This can help understanding differences between circuits and machines, or between classical logics and fixed point logics.</li>
<li><strong>Algebra and Coalgebra.</strong> Regular languages form a syntactic monoid, which is an algebraic structure. Finite automata form what in the language of category theory is called a coalgebra. In the case of a deterministic automaton, we can easily move between an algebraic and a coalgebraic representation, but in the case of NFAs, this is not so easy. </li>
<li><strong>The Arithmetic Perspective.</strong> There is a deep connection between computation and number-theory. You may choose to understand this as a statement about the power of number theory, and/or the universality of computation. You usually know that finite automata can recognize an even number of symbols, and that they cannot count enough to match parenthesis. But how much arithmetic are they capable of? Finite automata can decide Presburger arithmetic formulae. The simplest decision procedure I know for Presburger arithmetic reduces a formula to an automaton. This is one glimpse from which you can progress to Hilbert's 10th problem and it's resolution which led to discovery of a connection between Diophantine equations and Turing machines. </li>
<li><strong>The Logical Perspective.</strong> Computation can be understood from a purely logical perspective. Finite automata can be characterised by weak, monadic second order logic over finite words. This is my favourite, non-trivial example of a logical characterisation of a computational device. Descriptive complexity theory shows that many complexity classes have purely logical characterisations too.</li>
<li><strong>Finite Automata are Hiding in Places you Never Imagined.</strong>  (Hat-tip to Martin Berger's comment on the connection to coding theory) The 2011 Nobel Prize in Chemistry was given to the discovery of quasi-crystals. The mathematics behind quasi-crystals is connected to aperiodic tilings. One specific aperiodic tiling of the plane is called the Cartwheel Tiling, which consists of a kite shape and a bow-tie shape. You can encode these shapes in terms of 0s and 1s and then study properties of these sequences, which code sequences of patterns. In fact, if you map 0 to 01 and 1 to 0, and repeatedly apply this map to the digit 0, you will get, 0, 01, 010, 01001, etc. Observe that the lengths of these strings follow the Fibonacci sequence. Words generated in this manner are called Fibonacci words. Certain shape sequences observed in Penrose tilings can be coded as Fibonacci words. Such words have been studied from an automat-theoretic perspective, and guess what, some families of words are accepted by finite automata, and even provide examples of worst-case behaviour for standard algorithms such as Hopcroft's minimization algorithm. Please tell me you are dizzy.</li>
</ol>

<p>I could go on.(And on.)* I find it useful to have automata in the back of my head and recall them every now and then to understand a new concept or to gain intuition about high-level mathematical ideas. I doubt that everything I mention above can be communicated in the first few lectures of a course, or even in a first course. These are long-term rewards based on an initial investment made in the initial lectures of an automata theory course.</p>

<p>To address your title: I don't always seek enlightenment, but when I do, I prefer finite automata. Stay thirsty, my friend.</p>

CC BY-SA 3.0
2012-12-23T10:48:49.890Z
Beautiful list. I would like to add that automata provide an interesting perspective on coding theory, pioneered by Schuetzenberger. In addition, modern theory of concurrency and process theory are a generalisation of automata theory where automata can be composed in parallel and synchronise on their actions.
Martin Berger
CC BY-SA 3.0
2012-12-23T12:15:39.177Z
Wow. (+ 0.5 for last sentence. :-)
LarsH
CC BY-SA 3.0
2012-12-24T16:27:32.463Z
Why can't I +10 this?
psoft
CC BY-SA 3.0
2012-12-26T11:28:38.397Z
Just joined TCS.SE solely in order to +1 this.
Tynam
CC BY-SA 3.0
2012-12-26T14:59:12.657Z
Despite knowing of pretty much everything in this list, still I somehow feel enlightened for having read it. (Also, (And on.)* made me chuckle.)
C. A. McCann
CC BY-SA 3.0
2012-12-27T20:50:35.513Z
Nice answer. I would prefer to ask, what is the advantage of finite automata than Turing machine? I mean, I learn TCS  beginning with Turing machine model. What is the insight that the finite automata model can provide us, but Turing machine model cannot?
Yao Wang
CC BY-SA 3.0
2012-12-27T21:44:15.630Z
@YaoWang, see items 4-8 above. I do not think you can obtain these insights from Turing machines.
Vijay D
CC BY-SA 3.0
2012-12-27T22:02:24.753Z
@VijayD Thanks for the quick and clear answer. Now I at least gain some intuition. Please correct me if I am wrong. The NFA/DFA model stresss more on representation of language than Turing machine, right?
Yao Wang
CC BY-SA 3.0
2014-03-07T15:34:27.303Z
Honestly, I had never thought about most of this stuff (and some of the theorems I've never heard of), and I did take a course in theory of computation. Does one have to have a particularly good teacher or curriculum to point out these revelations?
Ken Bloom
CC BY-SA 3.0
2015-01-06T16:06:23.420Z
I came here to gain some insight on item#9. Though I learned more than that (way more) I still can't think of a processor as a automaton. Can you please help? thanks.
hkoosha
CC BY-SA 3.0
2012-12-23T10:37:59.563Z
2016-01-13T22:40:04.250Z
2016-01-13T22:40:04.250Z
Vijay D
<p>I've been revising Theory of Computation for fun and this question has been nagging me for a while (funny never thought of it when I learnt Automata Theory in my undergrad). So "why" exactly do we study deterministic and non-deterministic finite automata (DFA/NFAs)? So here are some answers I came up with after soliloquing  but still fail to see their overall contribution to the 'aha' moment:</p>

<ol>
<li>To study what they are and aren't capable of i.e. limitations 
<ul>
<li>Why?</li>
</ul></li>
<li>Since they are the basic models of theoretical computation and would lay the foundation of other more capable models of computation.
<ul>
<li>What makes them 'basic'? Is it that they have only one bit of storage and state transitions?</li>
</ul></li>
<li>Okay, so what? How does all this contribute to answer the question of computability? It seems Turing machines help understand this really well and there are 'lesser' models of computations like PDAs, DFA/NFAs/Regexes etc. But if one didn't know FAs what is it that they are missing out on?</li>
</ol>

<p>So although I 'get it' to some extent, I am unable to answer this question to myself? How best would you explain 'why study D/N-FAs'? What's the question they seek to answer? How does it help and why is it the first thing taught in Automata Theory?</p>

<p>PS: I'm aware of the various lexicographic applications and pattern matchers that can be implemented as such. However, I don't wish to know what it can be used for practically but what was their reason for use/invention/design during the culmination of studying the theory of computation. Historically speaking what led one to start with this and what 'aha' understanding is it supposed to lead to? If you were to explain their importance to CS students just beginning to study Automata Theory, how'd you do it? </p>

CC BY-SA 3.0
2012-12-23T17:19:56.500Z
So, this is a research level question in TCS?
Hendrik Jan
CC BY-SA 3.0
2012-12-23T19:38:26.973Z
@HendrikJan - I'm just curious :) Not sure if it should be categorized as such.
PhD
CC BY-SA 3.0
2012-12-23T20:40:48.940Z
It's not so much a research question as one asking for a big-picture perspective on a topic. We have a number of such questions here. Rather than start a debate in the comments, I'd encourage you to post a question on meta if you'd like to discuss the appropriateness of such questions further.
Suresh Venkat
CC BY-SA 3.0
2012-12-23T21:57:57.600Z
PhD: Your question gave some very good answers, so I thank you for it. You were honest in your statements, and it was not my intention to disqualify you or your question. Actually it is the other way around from what my comment suggests: I have seen some other questions that were dismissed too easily using this quote from the faq. You are right Suresh: this is not the place for starting a debate. Sorry.
Hendrik Jan
CC BY-SA 3.0
2012-12-24T00:05:31.307Z
@HendrikJan - Oh don't worry! Text hides tone. I never meant it that way. I thought you were asking me if this was a research question on my part.
PhD
CC BY-SA 3.0
2012-12-24T07:25:29.777Z
@Hendrik, I can't see any question that you have posted. Questions asking for insights are acceptable, take for example the question about padding and Russell's answer to it. If you have a question that would need a TCS researcher to answer and is interesting to other researchers then it is likely to be on-topic. Questions by graduate student who are looking for deeper understanding and insights are also on-topic. If you have doubts about suitability you can ask on [meta] to make it is on-topic, however you don't really need to; directly ask your question, in the worst case it may get closed.
Kaveh
CC BY-SA 3.0
2012-12-24T09:57:31.580Z
@Kaveh: Thanks for the additional explanation. I will be posting on META when I have doubts in the future. This (now famous) question is fine with me (see above) and in particular the answer by Vijay is great.
Hendrik Jan
CC BY-SA 3.0
2012-12-24T17:23:59.137Z
the simile Ive always pictured is that FSMs are like the Algebra to complexity theory's advanced areas analogous to Calculus or Differential Equations [or something even more advanced]. one cannot expect to work in higher math without mastering the basics, similarly in complexity theory. another neat relationship (not widely taught) is that a TM can be seen as a FSM transducer working iteratively/sequentially on an infinite tape.
vzn
CC BY-SA 3.0
2012-12-24T19:34:49.770Z
Somewhat related: http://cstheory.stackexchange.com/questions/8539/how-practical-is-automata-theory
Radu GRIGore
CC BY-SA 3.0
2012-12-25T04:12:55.067Z
Kudos to PhD and Hendrik for a level of civility I rarely encounter on public forums.
Lucas
CC BY-SA 3.0
2012-12-27T20:49:15.043Z
I recently want to ask this question. But I want to ask, what is the advantage of finite automata that Turing machine? I mean, I learn TCS  beginning with Turing model. What is the insight that the finite automata model can provide us, but Turing machine model cannot?
Yao Wang
CC BY-SA 3.0
2012-12-27T23:11:36.380Z
@YaoWang, I suggest you make a separate question. Your second comment below my answer indicates to me that you are seeking a basic rather than a research-level understanding, in which case, I recommend cs.stackexchange.com for your question.
Vijay D
CC BY-SA 3.0
2013-03-06T18:35:55.863Z
see also [practical applications of FSMs](http://cs.stackexchange.com/questions/10280/practical-application-of-finite-state-machines), cs.se
vzn
<fl.formal-languages><automata-theory><big-picture><teaching><dfa>
What is the enlightenment I'm supposed to attain after studying finite automata?
PhD
# What is the enlightenment I'm supposed to attain after studying finite automata?

(Asked by: username_0 on 2012-12-23)

I've been revising Theory of Computation for fun and this question has been nagging me for a while (funny never thought of it when I learnt Automata Theory in my undergrad). So "why" exactly do we study deterministic and non-deterministic finite automata (DFA/NFAs)? So here are some answers I came up with after soliloquing but still fail to see their overall contribution to the 'aha' moment:

1. To study what they are and aren't capable of i.e. limitations
   * Why?
2. Since they are the basic models of theoretical computation and would lay the foundation of other more capable models of computation.
   * What makes them 'basic'? Is it that they have only one bit of storage and state transitions?
3. Okay, so what? How does all this contribute to answer the question of computability? It seems Turing machines help understand this really well and there are 'lesser' models of computations like PDAs, DFA/NFAs/Regexes etc. But if one didn't know FAs what is it that they are missing out on?

So although I 'get it' to some extent, I am unable to answer this question to myself? How best would you explain 'why study D/N-FAs'? What's the question they seek to answer? How does it help and why is it the first thing taught in Automata Theory?

PS: I'm aware of the various lexicographic applications and pattern matchers that can be implemented as such. However, I don't wish to know what it can be used for practically but what was their reason for use/invention/design during the culmination of studying the theory of computation. Historically speaking what led one to start with this and what 'aha' understanding is it supposed to lead to? If you were to explain their importance to CS students just beginning to study Automata Theory, how'd you do it?

**Tags:** fl.formal-languages, automata-theory, big-picture, teaching, dfa
> **Comments:**
> **username_1**: So, this is a research level question in TCS?  
> **username_0**: @HendrikJan - I'm just curious :) Not sure if it should be categorized as such.  
> **username_2**: It's not so much a research question as one asking for a big-picture perspective on a topic. We have a number of such questions here. Rather than start a debate in the comments, I'd encourage you to post a question on meta if you'd like to discuss the appropriateness of such questions further.  
> **username_1**: PhD: Your question gave some very good answers, so I thank you for it. You were honest in your statements, and it was not my intention to disqualify you or your question. Actually it is the other way around from what my comment suggests: I have seen some other questions that were dismissed too easily using this quote from the faq. You are right Suresh: this is not the place for starting a debate. Sorry.  
> **username_0**: @HendrikJan - Oh don't worry! Text hides tone. I never meant it that way. I thought you were asking me if this was a research question on my part.  
> **username_3**: @Hendrik, I can't see any question that you have posted. Questions asking for insights are acceptable, take for example the question about padding and Russell's answer to it. If you have a question that would need a TCS researcher to answer and is interesting to other researchers then it is likely to be on-topic. Questions by graduate student who are looking for deeper understanding and insights are also on-topic. If you have doubts about suitability you can ask on [meta] to make it is on-topic, however you don't really need to; directly ask your question, in the worst case it may get closed.  
> **username_1**: @Kaveh: Thanks for the additional explanation. I will be posting on META when I have doubts in the future. This (now famous) question is fine with me (see above) and in particular the answer by Vijay is great.  
> **username_4**: the simile Ive always pictured is that FSMs are like the Algebra to complexity theory's advanced areas analogous to Calculus or Differential Equations [or something even more advanced]. one cannot expect to work in higher math without mastering the basics, similarly in complexity theory. another neat relationship (not widely taught) is that a TM can be seen as a FSM transducer working iteratively/sequentially on an infinite tape.  
> **username_5**: Somewhat related: http://cstheory.stackexchange.com/questions/8539/how-practical-is-automata-theory  
> **username_6**: Kudos to PhD and Hendrik for a level of civility I rarely encounter on public forums.  
> **username_7**: I recently want to ask this question. But I want to ask, what is the advantage of finite automata that Turing machine? I mean, I learn TCS  beginning with Turing model. What is the insight that the finite automata model can provide us, but Turing machine model cannot?  
> **username_8**: @YaoWang, I suggest you make a separate question. Your second comment below my answer indicates to me that you are seeking a basic rather than a research-level understanding, in which case, I recommend cs.stackexchange.com for your question.  
> **username_4**: see also [practical applications of FSMs](http://cs.stackexchange.com/questions/10280/practical-application-of-finite-state-machines), cs.se  

---

## 11 answers

### Answer by username_8 on 2012-12-23. Score: 360 | Accepted answer

I have personally enjoyed several *Aha!* moments from studying basic automata theory. NFAs and DFAs form a microcosm for theoretical computer science as a whole.

1. **Does Non-determinism Lead to Efficiency?** There are standard examples where the minimal deterministic automaton for a language is exponentially larger than a minimal non-deterministic automaton. Understanding this difference for Turing machines is at the core of (theoretical) computer science. NFAs and DFAs provide the simplest example I know where you can explicitly see the strict gap between determinism and non-determinism.
2. **Computability != Complexity.** NFAs and DFAs both represent regular languages and are equivalent in *what* they compute. They differ in *how* they compute.
3. **Machines Refine Languages.** This is a different take on what we compute and how we compute. You can think of computable languages (and functions) as defining an equivalence class of automata. This is a fundamental perspective change in TCS, where we focus not just on the what, but the how of computation and try to choose the right 'how' when designing an algorithm or understand the space of different how's in studying complexity classes.
4. **The Value of Canonical Representation.** DFAs are the quintessential example of a data-structure admitting a canonical representation. Every regular language has a unique, minimal DFA. This means that given a minimal DFA, important operations like language inclusion, complementation, and checking acceptance of a word become trivial. Devising and exploiting canonical representations is a useful trick when developing algorithms.
5. **The Absence of Canonical Representations.** There is no well accepted canonical representation of regular expressions or NFA. So, despite the point above, canonical representations do not always exist. You will see this point in many different areas in computer science. (for example, propositional logic formulae also do not have canonical representations, while ROBDDs do).
6. **The Cost of a Canonical Representation.** You can even understand the difference between NFAs and DFAs as an algorithmic *no-free-lunch* theorem. If we want to check language inclusion between, or complement an NFA, you can determinize and minimize it and continue from there. However, this "reduction" operation comes at a cost. You will see examples of canonization at a cost in several other areas of computer science.
7. **Infinite != Undecidable.** A common misconception is that problems of an infinitary nature are inherently undecidable. Regular languages contain infinitely many strings and yet have several decidable properties. The theory of regular languages shows you that infinity alone is not the source of undecidability.
8. **Hold Infinity in the Palm of Your Automaton.** You can view a finite automaton purely as a data-structure for representing infinite sets. An ROBDD is a data-structure for representing Boolean functions, which you can understand as representing finite sets. A finite-automaton is a natural, infinitary extension of an ROBDD.
9. **The Humble Processor.** A modern processor has a lot in it, but you can understand it as a finite automaton. Just this realisation made computer architecture and processor design far less intimidating to me. It also shows that, in practice, if you structure and manipulate your states carefully, you can get very far with finite automata.
10. **The Algebraic Perspective.** Regular languages form a syntactic monoid and can be studied from that perspective. More generally, you can in later studies also ask, what is the right algebraic structure corresponding to some computational problem.
11. **The Combinatorial Perspective.** A finite-automaton is a labelled graph. Checking if a word is accepted reduces to finding a path in a labelled graph. Automata algorithms amount to graph transformations. Understanding the structure of automata for various sub-families of regular languages is an active research area.
12. **The Algebra-Language-Combinatorics love triangle.** The Myhill-Nerode theorem allows you to start with a language and generate an automaton or a syntactic monoid. Mathematically, we obtain a translation between very different types of mathematical objects. It is useful to keep such translations in mind and look for them in other areas of computer science, and to move between them depending on your application.
13. **Mathematics is the Language of Big-Pictures.** Regular languages can be characterised by NFAs (graphs), regular expressions (formal grammar), read-only Turing machines (machine), syntactic monoids (algebra), Kleene algebras (algebra), monadic second-order logic, etc. The more general phenomenon is that important, enduring concepts have many different mathematical characterizations, each of which brings different flavours to our understanding of the idea.
14. **Lemmas for the Working Mathematician.** The Pumping Lemma is a great example of a theoretical tool that you can leverage to solve different problems. Working with Lemmas is good practice for trying to build upon existing results.
15. **Necessary != Sufficient.** The Myhill-Nerode theorem gives you necessary and sufficient conditions for a language to be regular. The Pumping Lemma gives us necessary conditions. Comparing the two and using them in different situations helped me understand the difference between necessary and sufficient conditions in mathematical practice. I also learnt that a *reusable* necessary and sufficient condition is a luxury.
16. **The Programming Language Perspective.** Regular expressions are a simple and beautiful example of a programming language. In concatenation, you have an analogue of sequential composition and in Kleene star, you have the analogue of iteration. In defining the syntax and semantics of regular expressions, you make a baby step in the direction of programming language theory by seeing inductive definitions and compositional semantics.
17. **The Compiler Perspective.** The translation from a regular expression to a finite automaton is also a simple, theoretical compiler. You can see the difference between parsing, intermediate-code generation, and compiler optimizations, because of the difference in reading a regular expression, generating an automaton, and then minimizing/determinizing the automaton.
18. **The Power of Iteration.** In seeing what you can do in a finite-automaton with a loop and one without, you can appreciate the power of iteration. This can help understanding differences between circuits and machines, or between classical logics and fixed point logics.
19. **Algebra and Coalgebra.** Regular languages form a syntactic monoid, which is an algebraic structure. Finite automata form what in the language of category theory is called a coalgebra. In the case of a deterministic automaton, we can easily move between an algebraic and a coalgebraic representation, but in the case of NFAs, this is not so easy.
20. **The Arithmetic Perspective.** There is a deep connection between computation and number-theory. You may choose to understand this as a statement about the power of number theory, and/or the universality of computation. You usually know that finite automata can recognize an even number of symbols, and that they cannot count enough to match parenthesis. But how much arithmetic are they capable of? Finite automata can decide Presburger arithmetic formulae. The simplest decision procedure I know for Presburger arithmetic reduces a formula to an automaton. This is one glimpse from which you can progress to Hilbert's 10th problem and it's resolution which led to discovery of a connection between Diophantine equations and Turing machines.
21. **The Logical Perspective.** Computation can be understood from a purely logical perspective. Finite automata can be characterised by weak, monadic second order logic over finite words. This is my favourite, non-trivial example of a logical characterisation of a computational device. Descriptive complexity theory shows that many complexity classes have purely logical characterisations too.
22. **Finite Automata are Hiding in Places you Never Imagined.** (Hat-tip to Martin Berger's comment on the connection to coding theory) The 2011 Nobel Prize in Chemistry was given to the discovery of quasi-crystals. The mathematics behind quasi-crystals is connected to aperiodic tilings. One specific aperiodic tiling of the plane is called the Cartwheel Tiling, which consists of a kite shape and a bow-tie shape. You can encode these shapes in terms of 0s and 1s and then study properties of these sequences, which code sequences of patterns. In fact, if you map 0 to 01 and 1 to 0, and repeatedly apply this map to the digit 0, you will get, 0, 01, 010, 01001, etc. Observe that the lengths of these strings follow the Fibonacci sequence. Words generated in this manner are called Fibonacci words. Certain shape sequences observed in Penrose tilings can be coded as Fibonacci words. Such words have been studied from an automat-theoretic perspective, and guess what, some families of words are accepted by finite automata, and even provide examples of worst-case behaviour for standard algorithms such as Hopcroft's minimization algorithm. Please tell me you are dizzy.

I could go on.(And on.)\* I find it useful to have automata in the back of my head and recall them every now and then to understand a new concept or to gain intuition about high-level mathematical ideas. I doubt that everything I mention above can be communicated in the first few lectures of a course, or even in a first course. These are long-term rewards based on an initial investment made in the initial lectures of an automata theory course.

To address your title: I don't always seek enlightenment, but when I do, I prefer finite automata. Stay thirsty, my friend.

> **Comments:**
> **username_19**: Beautiful list. I would like to add that automata provide an interesting perspective on coding theory, pioneered by Schuetzenberger. In addition, modern theory of concurrency and process theory are a generalisation of automata theory where automata can be composed in parallel and synchronise on their actions.  
> **username_20**: Wow. (+ 0.5 for last sentence. :-)  
> **username_21**: Why can't I +10 this?  
> **username_22**: Just joined TCS.SE solely in order to +1 this.  
> **username_23**: Despite knowing of pretty much everything in this list, still I somehow feel enlightened for having read it. (Also, (And on.)* made me chuckle.)  
> **username_7**: Nice answer. I would prefer to ask, what is the advantage of finite automata than Turing machine? I mean, I learn TCS  beginning with Turing machine model. What is the insight that the finite automata model can provide us, but Turing machine model cannot?  
> **username_8**: @YaoWang, see items 4-8 above. I do not think you can obtain these insights from Turing machines.  
> **username_7**: @VijayD Thanks for the quick and clear answer. Now I at least gain some intuition. Please correct me if I am wrong. The NFA/DFA model stresss more on representation of language than Turing machine, right?  
> **username_24**: Honestly, I had never thought about most of this stuff (and some of the theorems I've never heard of), and I did take a course in theory of computation. Does one have to have a particularly good teacher or curriculum to point out these revelations?  
> **username_16**: I came here to gain some insight on item#9. Though I learned more than that (way more) I still can't think of a processor as a automaton. Can you please help? thanks.  

---

### Answer by username_9 on 2012-12-23. Score: 36

There are many good theoretical reasons to study N/DFAs. Two that immediately come to mind are:

1. Turing machines (we think) capture everything that's computable. However, we can ask: What parts of a Turing machine are "essential"? What happens when you limit a Turing machine in various ways? DFAs are a very severe and *natural* limitation (taking away memory). PDAs are a less severe limitation, etc. It's theoretically interesting to see what memory gives you and what happens when you go without it. It seems a very *natural* and basic question to me.
2. Turing machines need an infinite tape. Our universe is finite, so in some sense every computing device is a DFA. Seems like an important, and again natural, topic to study.

Asking why one should study DFAs is akin to asking why one should learn Godel's [completeness](http://en.wikipedia.org/wiki/G%C3%B6del%27s_completeness_theorem) theorem when the real interesting thing is his [incompleteness](http://en.wikipedia.org/wiki/G%C3%B6del%27s_incompleteness_theorems) theorem.

The reason they are the first topic in automata theory is because it's natural to build up to more complicated modes from less complicated ones.

> **Comments:**
> **username_0**: #1 makes good sense and I think I see the reason. But how would you explain the reason 'going forward' from FAs? Those who know something about ToC can backtrack in retrospect and mull on it. How best to explain the 'why' to students who start learning automata theory and only know FAs? Do we just state we are starting with one bit machines since they are basic - why? How best to answer 'that' why? Would appreciate some light when answering this question for total noobs to ToC :)  
> **username_2**: The "forward" argument comes from the fact (as Sariel mentioned) that state machines are perhaps the most basic of computing devices. You're in a state: something happens, and then you move to a new state. Note that markov chains (which are very important in machine learning) are just probabilistic FSMs.  

---

### Answer by username_10 on 2012-12-23. Score: 34

To add one more perspective to the rest of the answers: because you can actually do stuff with finite automata, in contrast with Turing machines.

Just about any interesting property of Turing machines are undecidable. On the contrary, with finite automata, just about everything *is* decidable. Language equality, inclusion, emptiness and universality are all decidable. Combined with that finite automata are closed under just about every operation you can think of, and that these operations are computable, you can do pretty much anything you'd ever want to do with finite automata.

This means that if you can capture something using finite automata, you automatically gain a lot of tools to analyze it. For instance, in software testing, systems and their specifications can be modeled as finite automata. You can then automatically test whether your system correctly implements the specification.

Turing machines and finite automata therefore teach people an interesting and ubiquitous contrast: more descriptive power goes hand in hand with less tractability. Finite automata can't describe much, but we can at least do stuff with them.

> **Comments:**
> **username_4**: "...you can actually do stuff with finite automata, in contrast with Turing machines." understand the pt, however a quote that sounds ironic or doesnt make much sense taken out of context...  

---

### Answer by username_13 on 2012-12-23. Score: 27

State. you need to learn that one can model the world (for certain problems) as a finite state space, and one can think about computation in this settings. This is a simple insight but extremely useful if you do any programming - you would encounter state again and again and again, and FA give you a way to think about them. I consider this to be a sufficient excuse for teaching a complete class. Of course, state can be deterministic or non-deterministic. Thus DFA and NFA, but you can convert between them, etc.

The second thing to learn is the Halting theorem. Which is related to the Godel incompleteness theorem. (You can not build a machine that can compute everything, and there are mathematical claims that you can neither proof nor disprove, and as such needed to be taken as axioms. That is, we live in a world that has no finite description or real oracles - yey for us!)

Now, I did my undergrad in math, and you get used to the idea that you learn stuff you have no clue why you are learning (group theory, measure theory, set theory, Hilbert spaces, etc, etc, etc [all good stuff, BTW]). There is something to be said about learning how to learn - next time you have to learn some bizarro math (because you need to use it to do something out there in the real world) that looks very strange you take in stride. Specifically, the third thing to learn is mathematical maturity - being able to argue carefully about things, know when proofs are correct or not, write down proofs, etc. If you have it already, this course is easy, and you would not care too much why you are learning it.

Except for these, the course is a complete waste of your time, like everything else. Specifically, you can live a happy life without knowing this stuff. But this is literally true of all knowledge. More or less. For me a course in university is worth its time, if you look on the world differently after learning it. This is definitely one of the courses that changed the way I think about the world. What more can you ask?


---

### Answer by username_11 on 2012-12-23. Score: 23

Although it is not really the reason they were originally studied, finite automata and the regular languages they recognize are tractable enough that they have been used as building blocks for more complicated mathematical theories. In this context see particularly [automatic groups](http://en.wikipedia.org/wiki/Automatic_group) (groups in which the elements can be represented by strings in a regular language and in which the products of elements by group generators can be computed by finite state transducers) and [sofic subshifts](http://en.wikipedia.org/wiki/Sofic_subshift#Characterization_and_sofic_subshifts) (subshifts of a shift space whose forbidden words form a regular language). So there are reasons to study them even if you are interested in pure mathematics rather than computer science.

Finite automata have also been used in the design of algorithms for other kinds of objects. For instance, [an algorithm of Culik for testing whether a one-dimensional cellular automaton is reversible](http://www.complex-systems.com/pdf/01-6-1.pdf) involves constructing, modifying, and testing the properties of certain NFAs. And a [1986 FOCS paper by Natarajan](http://dl.acm.org/citation.cfm?id=1382439.1382941) showed how to solve a certain problem in the design of mechanical assembly lines by reducing it to a computation about finite automata.


---

### Answer by username_5 on 2012-12-23. Score: 18

You are asking (at least) two different questions: (a) What parts of theory build on finite automata nowadays? (b) Why were finite automata developed in the first place? I think the best way to address the latter is to look at the old papers, such as:

* Rabin, Scott, [Finite Automata and Their Decision Problems](http://www.google.co.uk/search?q=Finite%20automata%20and%20their%20decision%20problems), 1959

Here are the first two paragraphs:

> Turing machines are widely considered to be the abstract prototype of
> digital computers; workers in the field, however, have felt more and
> more that the notion of a Turing machine is too general to serve as an
> accurate model of actual computers. It is well known that even for
> simple calculations it is impossible to give an *a priori* upper bound
> on the amount of tape a Turing machine will need for any given
> computation. It is precisely this feature that renders Turing's
> concept unrealistic.
>
> In the last few years the idea of a *finite automaton* has appeared in
> the literature. These are machines having only a finite number of
> internal states that can be used for memory and computation. The
> restriction on finiteness appears to give a better approximation to
> the idea of a physical machine. Of course, such machines cannot do as
> much as Turing machines, but the advantage of being able to compute an
> arbitrary general recursive function is questionable, since very few
> of these functions come up in practical applications.

In short, they were developed as a model of real computers, which have finite resources.


---

### Answer by username_12 on 2012-12-23. Score: 16

Another reason is that they're relatively *practical* theoretical models. A Turing machine, apart from the impossibility of the infinite tape, is kind of an awkward fit for what it's like to program a computer (note that this is not a good analogy to begin with!). PDAs and DFAs however are quite amenable to being models of actual programs in the sense that a PDA/DFA design can often easily be turned into a real program. Compiler design, for example, uses them extensively. So at these sort of connection points between theory and practice, we get a handle on how it all ties together, and what we can and can't do.


---

### Answer by username_14 on 2012-12-24. Score: 10

Check out the "Living Binary Adder" Game here : <http://courstltc.blogspot.com/2012/12/living-binary-adder-game.html>
I used to present this game to my students in the early chapters about DFA/NFA. It illustrates two important things in Automata Theory:

1. How to transform a mental process into a simple mechanical one
2. What abstraction really means. Two states, as C and Z states above, can be anything : transistors in a computer, an hydraulic mechanism or two human players !

This, sometimes bring the "Aha" moment to my students.


---

### Answer by username_15 on 2012-12-24. Score: 9

The concept of DFAs is very useful for designing efficient solutions to many types of problems. One example is networking. Every protocol can be implemented as a state machine. Implementing the solution this way makes the code simpler and simpler means a lower defect rate. It also means that changes to the code are easier and have a lower impact, again having a lower defect rate.

Some people find it difficult to view a network protocol as a state machine but those who can make the jump find it very rewarding in terms of return on effort.

> **Comments:**
> **username_16**: Sounds very ingesting but can you explain a little more? it *is* hard to imagine a network protocol as a state machine. thank you.  

---

### Answer by username_17 on 2016-01-14. Score: 3

Actually, my students sometimes ask precisely this -- after spending a large chunk of the semester on finite automata and finally arriving at Turing machines. Why spend so much time on a weaker formalism when a stronger one is available? So I explain the inherent tradeoff in expressive power vs. analytic complexity. The richer models are typically more difficult to analyze. The DFA vs. TM dichotomy is extreme, as the membership problem is trivial for one and uncomputable for the other. A less extreme example would be DFA vs. PDA. The membership problem for the latter turns out to be efficiently solvable, but the solution is not at all trivial. We see this occurrennce in many branches of math and science: study a simple model to get as complete an understanding as possible, which usually leads to insights into more complex models as well.


---

### Answer by username_18 on 2012-12-26. Score: -4

I see several answers calling FM's "lesser" than Turing machines.

A primary focus in the Post-grad class I took lay in their equivalence, not distinctions. For every FSM model we studied, we had to prove their equivalence to Turing Machines. This is done by implementing a Turing Machine in the FSM. IIRC, we also studied some other computing models that cold not implement a TM, but I forget what those were. The point is, if you can implement a TM, you can run any TM program on the model, given a sufficiently large tape analog for the problem being run.

The thrust of the answer to the question was: TM is the basic computability model, but not very practical when it comes to building useful machines. Hence FSM models.

This was brought home viscerally to me when, at around the same time (1984), I discovered the FORTH language. It's execution engine is built on a pure realization of a Dual Stack PDA. Going deeper I fond this same engine under expression compilers

Although, for me, the real impact of FSM was discovering the book "Theory of Finite Automata" by Trakhtenbrot and Korzynski (?) when I was 18, a discovery that essentially gave me my career.

> **Comments:**
> **username_8**: I assume though that you did not prove an equivalence between Nondeterministic Finite Automata and Turing Machines. It is this specific object the OP asked about and that the rest of us are calling "lesser".  
> **username_2**: And an FA is not the same as an FSM.  

---

