What is the enlightenment I'm supposed to attain after studying finite automata?

Question

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?

Answer 1

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.

Answer 2

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 theorem when the real interesting thing is his incompleteness 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.

Answer 3

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.

Answer 4

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 5

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 (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 (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 involves constructing, modifying, and testing the properties of certain NFAs. And a 1986 FOCS paper by Natarajan showed how to solve a certain problem in the design of mechanical assembly lines by reducing it to a computation about finite automata.

Answer 6

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, 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 7

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 8

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 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.

Answer 10

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 11

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.