40
$\begingroup$

There is always a way for application in topics related to theoretical computer science. But textbooks and undergraduate courses usually don't explain the reason that automata theory is an important topic and whether it still has applications in practice. Therefore undergraduate students might have trouble in understanding the importance of automata theory and might think it is not of any practical use anymore.

Is automata theory still useful in practice?

Should it be part of undergraduate CS curriculum?

Improve this question
$\endgroup$
9
  • 4
    $\begingroup$ I think this is off-topic here; please see the FAQ. $\endgroup$
    – Jukka Suomela
    Oct 9, 2011 at 22:33
  • 4
    $\begingroup$ I have mixed feelings about the 'off=topic'-ness of this. It's obviously not research level, but this particular question of the relevance of automata theory is one that comes up often. $\endgroup$
    – Suresh Venkat
    Oct 10, 2011 at 0:33
  • 19
    $\begingroup$ I think this is perfectly on-topic. What are the applications of finite automata theory? No different from Vertex Cover Applications in the Real World, and we didn't close that question. $\endgroup$
    – Peter Shor
    Oct 10, 2011 at 14:27
  • 4
    $\begingroup$ By the way, this question is closely related, and its answers might give some practical motivation for the study of finite automata theory as well: "What are regular expressions good for?". $\endgroup$
    – Jukka Suomela
    Oct 10, 2011 at 14:39
  • 2
    $\begingroup$ I have to say that the quality and variety of answers makes the "scope" issue irrelevant. I hope that with three close votes already, this question doesn't teeter over the edge. $\endgroup$
    – Suresh Venkat
    Oct 11, 2011 at 14:00

14 Answers 14

Reset to default
56
$\begingroup$

  1. Ever used a tool like grep/awk/sed? Regular expressions form the heart of these tools.

  2. You'll be surprised how much coding you can avoid by principled use of regular expressions - in "practical projects", like an email server.

  3. If you're a CS major, you'll definitely be writing a compiler/interpreter for a (at least a small) language. If you've ever tried this task before and got stuck, you'll appreciate how much a little theory (aka context free grammars) can help you. This theory has made a once impossible task into something that can be completed over a weekend. (And it won the inventor a Turing award - google BNF).

  4. If you're a CS major, at some point, you need to sit back and think about the philosophical foundations of computing, and not just about how cool the next version of the Android API is. On a related note, it is the job of the university not to prepare you for the next 5 years of your life, but to prepare you for the next 50. The only thing they can do in this regard is to help you think - think of automata theory as one of those courses.

Improve this answer
$\endgroup$
0
34
$\begingroup$

Can you hear that noise? It is the sound of a thousand brilliant theorems, applications and tools laughing in automata-theoretic heaven.

Languages and automata are elegant and robust concepts that you will find in every area of computer science. Languages are not dry, formalist hand-me-downs from computing prehistory. The language theory perspective distills seemingly complicated questions about sophisticated, opaque objects into simple statements about words and trees. Formal languages play a role in computer science akin to the fundamental and game-changing viewpoint brought by algebra and topology to classical mathematics. Here are some practical, fairly complicated, practical problems that are approached via language theory.

  1. You want to spot duplicate occurrences of a phrase in a document and delete the second occurrence. In essence, you want to substitute a sequence in a language.
  2. Does a program contain an assertion violation? Does a device driver respect certain protocols when interacting with the kernel? The behaviour of a program is a set of executions; in other words, a language. The correctness property is another language. The program correctness problem amounts to a language inclusion check.
  3. Can your software be stuck in an infinite loop? Does a distributed algorithm contain a livelock? We need languages over infinite words, but the language inclusion view still applies.
  4. You want to build a sanitizer to detect malicious Javascript entered into a web application. The set of malicious strings is a language. The set of strings entered into the forms in another language. You want to determine if the intersection of these languages is non-empty.
  5. Run-time monitoring of reactive and mission-critical systems. You want to design a software monitor that oversees the operation of your chemical process or track updates to a financial database. These are at heart language inclusion and intersection problems.
  6. Pattern recognition with its numerous applications. You want to detect patterns in genomic data, in text, in a series of bug reports. These are problems where we are given words from an unknown language and have to guess the language. These are language inference problems.
  7. Given a set of XML documents, you want to reverse engineer a schema that applies to these documents. XML documents can be idealised a trees. A schema is then a specification of a tree language and the schema inference problem is a language inference problem over tree languages.
  8. Many applications require automated arithmetic reasoning. Suppose we fix a logical theory such as Presburger arithmetic, in which we have the natural numbers, addition and the less-than predicate. A formula with n variables represents a set of n-dimensional vectors. A vector is a sequence of digits and can be encoded as a word. A predicate is then a set of words; a language. Logical operations such as conjunction, disjunction and negation become intersection, union and complement of languages (existential quantification is a kind of projection).

The reduction hinted at above treats languages as abstract mathematical objects. To apply these ideas in practice, we need a data structure to represent languages and algorithms to manipulate these data structures.

Enter automata. Automata allow us to reduce questions about abstract mathematical objects like languages to concrete, algorithmic questions about labelled graphs. Languages and automata theory, besides an insane number of practical applications, provide a very significant intellectual service. We can think about problems ranging from formatting zip codes to decision procedures for monadic second order logic in uniform and uncluttered conceptual space. How amazing is that!

I have said nothing about logic and decision procedures. (Yes, they have practical applications.) See Kaveh's answer for an authoritative overview.

Improve this answer
$\endgroup$
1
  • $\begingroup$ haha, the irony $\endgroup$
    – Praveen Soni
    Apr 18, 2018 at 12:50
33
$\begingroup$

One of the more practical manifestation of CS is Compiler Construction. In 1965, Knuth started the study of LR parsers. Quickly (in less than a decade), we had LALR parsers which are a subset of deterministic pushdown automata that allows us to implement shift/reduce parsers.

At the heart of the feasibility and efficiency of LALR parsing is a proof (by Knuth) that "prefixes" of the language turn out to be regular (your finite automaton). This is the genesis of automated parser generators like yacc/bison etc.

It is safe to say that programming languages as we know them owe much of their compiling efficiencies to these developments.

Here is another example: the heart of the TCP/IP protocol is a finite state machine. How much more practical can it get?

Every serious CS student, especially the practical ones, should pay attention to automata theory. It is the basis for much of the richness of Computer Science.

Improve this answer
$\endgroup$
1
  • $\begingroup$ Parsing of source files is not really the interesting (and important) part of a compiler, so I don't think that it is safe to say that "programming languages as we know them owe much of their compiling efficiencies to these developments". Moreover, it is possible to parse languages using different tools, for example PEGs or parsing combinators (i.e. parsec). $\endgroup$
    – Jan Špaček
    Jun 1, 2016 at 10:47
18
$\begingroup$

As was explained in the other answers, automata theory is important conceptually as a simple computational model that we understand well, and regular expressions and automata have many real-life applications.

Here's a small example for modern research that goes back to automata theory to understand a modern concept. In this paper researchers prove that regular languages all have property testers: "Regular languages are testable with a constant number of queries"

Improve this answer
$\endgroup$
16
$\begingroup$

It's not just vanilla automatons. You're learning about the basics (accepting states, epsilon-transitions, ...) of a (computational) model which helps in reasoning about what can, and more importantly what cannot be expressed with some query languages. A few interesting results include:

(and of course I'm skipping a lot of other classes)

Basically, it's a very general model. Your classes will probably emphasize the link between automata, languages and logic.

If I were looking at relating this to concrete "worldly" tools, I'd spend a leisurely morning at the library reading a couple parts (A-B?) from Foundations of Databases by Abiteboul & al, and trying to connect this back to class material. Of course it's just one of the (many) ways of looking for applications of an automata class, and I guess not the most obvious - but that's precisely why it's an interesting exercise.

Improve this answer
$\endgroup$
14
$\begingroup$

As already pointed out in various answers, Automata Theory in UG courses gives one the basic conceptual framework for introducing more advanced (and practical) topics, and also for pointing out overlooked connections; for instance: Binary Decision Diagrams (they are minimized DFA; after teaching DFA, I often teach BDD-based puzzle solving); scripting including in BioPerl and BioPython (and a great setting in which to reinforce how many unintended matches may be hidden in real-world script regexps), formal debugging (state properties as negated FA, intersect), and even VCR or home intruder alarm programming (every day stress situation of a poorly specified automaton taught through incomplete examples; perhaps formalized using Harel's play-in/play-out scenario based synthesis of user interfaces). I also use the setting to teach Python's (almost) purely functional subset, including maps, lambdas, and set comprehensions, using which one can code up standard FA algorithms, often in a manner virtually indistinguishable from math defns.

Improve this answer
$\endgroup$
2
  • 1
    $\begingroup$ Welcome, Ganesh ! $\endgroup$
    – Suresh Venkat
    Oct 11, 2011 at 13:58
  • 2
    $\begingroup$ A nice way of teaching automata. Would you be willing to share your lecture notes? $\endgroup$
    – Martin Berger
    Oct 11, 2011 at 14:11
10
$\begingroup$

There has been considerable research related to automata theory in model checking used in the industry. Check Moshe Vardi's recent lectures at Fields Institute, in particular the 3rd lecture "Logic, Automata, Games, and Algorithms" for a taste of why automata theory is still important and useful.

Abstract:

The automata-theoretic approach to decision procedures, introduced by Buechi, Elgot, Rabin and Trakhtenbrot in the 1950s and 1960s, is one of the most fundamental approaches to decision procedures. Recently, this approach has found industrial applications in formal verification of hardware and software systems. The path from logic to practical algorithms goes not only through automata, but also through games, whose algorithmic aspects were studies by Chandra, Kozen, and Stockmeyer in the late 1970s. In this overview talk we describe the path from logic to algorithms via automata and games.

The slides and audio files of lectures are available here: 1, 2, 3.

Improve this answer
$\endgroup$
9
$\begingroup$

I'll throw out another answer from an entirely different practical angle: finite state machines (or at least some simple generalizations/extensions of them) are often used on the AI side of game programming. They turn out to provide an excellent model for encapsulating character behavior; for instance, an enemy might have states representing 'patrol', 'search', 'approach', 'attack', 'defend', 'retreat', 'die', etc. with well-defined transitions between them. This doesn't involve any of the formal aspects of automata like regular languages and the like, but the concept of the automaton is a very core one.

Improve this answer
$\endgroup$
8
$\begingroup$

We have seen that the language which contrasts theory and practice, setting the one above the other, is the very consummation of ignorance—that it proves a man to be unacquainted with the very first elements of thought, and goes a great way towards proving his mind to be so perverted as to be incapable of being taught them.

— James Mill (writing pseudonymously as “P.Q.”), “Theory and Practice”, London and Westminster Review, April 1836

Improve this answer
$\endgroup$
6
$\begingroup$

We should take into account the semantics of the words "practical" and "application". For some students, practical is anything that will help them pass their exams; for others, anything that will come up in a job. In both cases, Automata Theory is very practical indeed.

As others point out, you will use grammars, for example, when studying compilers. But even more than that: understanding the whole concept of having different states and rules for transitions between them can make you a better programmer when you realize, for example, that your code is redundant here and there, and that when you improve it, you are applying in your code the same conceptual ideas behind DFA minimization.

Similarly for "application". What do you understand by that word? Even if you are a "down-to-earth engineer" you will see and use ideas similar to those of Automata Theory in real world projects: programming code, flow diagrams, and even the simple yet brilliant concept of a stack. For theory nerds like me, I consider applications of Automata Theory in other areas, like logic, algebra and finite model theory. Surely, I will probably never need to use the pumping lemma while shopping in a supermarket, but theorems like that have helped me understand the structure of certain classes of languages, not to mention the logics and algebraics structures they are in correspondence with. And that is something I value more than any measure of practicality.

Improve this answer
$\endgroup$
5
$\begingroup$

Thrown together with logics, automata can offer ways to check statemens like

$\qquad A \models \varphi$

for an automaton $A$ and a formula $\varphi$. If $A$ is a model of a system and $\varphi$ a formalisation of desired properties you get system verification, a very practical concern with a growing number of feasible applications.

Considering the automata side of things leads to nice algorithms. For example, if $\varphi$ is an LTL formula and $A$ a Büchi automaton (i.e. an infinitely running finite automaton) you can translate $\varphi$ to an equivalent automaton $A_\varphi$ and check wether $\cal{L}(A) \subseteq \cal{L}(A_\varphi)$

Improve this answer
$\endgroup$
4
$\begingroup$

Finite Automata, often written about as finite state machines in different contexts, or with their probabilistic variants Hidden Markov Models can be applied to pattern recognition and quantifying structure of a pattern. E.g. what is the smallest stochastic finite automata that will generate strings according, more or less, to a given probability distribution, or matching statistical properties of a sample of strings (or time series) from some distribution.

See for example CSSR, an algorithm for blindly reconstruction hidden states; it's more efficient and flexible than Hidden Markov Models.

Improve this answer
$\endgroup$
1
  • 1
    $\begingroup$ To add to the practial side, Hidden Markov Models are used in speech recognition programs such as Kurzweil. $\endgroup$
    – tdyen
    Oct 11, 2011 at 22:53
3
$\begingroup$

Another more practical application of automata theory is the development of artificial intelligence. Artificial Intelligence was developed from the concept of finite automaton. The neural network of robots is constructed on the basis of automata theory. After all robots are also automata.

Improve this answer
$\endgroup$
2
$\begingroup$

Some have given great answers when it comes to how it relates to industry. What should be important is its scientific value, and Automata theory is often the doorway to first understand a higher tier of theory of computation in an undergraduate student's studies. Automata theory has a grand set of theorems that pop up all over the place in Theoretical Computer Science, and especially when one wants to talk about application such as Compilers. Its scientific value (its not outdated, how could it be? It's core theory to the field.) is practical to any scientist that is interested in computation. It is practical as it is knowledge that is useful to those who understand or want to understand the nature of computation. If you cannot find use in it, I question ones research or even intent to study CS as it's not programming (that's an application of CS), it's a formal science.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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