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

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

<ol>
<li>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.</li>
<li>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.</li>
<li>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. </li>
<li>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.</li>
<li>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.</li>
<li>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. </li>
<li>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. </li>
<li>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).</li>
</ol>

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

<p>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!</p>

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

CC BY-SA 3.0
2018-04-18T12:50:18.227Z
haha, the irony
Praveen Soni
CC BY-SA 3.0
2011-10-11T04:41:01.983Z
2011-10-11T15:59:56.310Z
2011-10-11T15:59:56.310Z
Vijay D
<p>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.</p>

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

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

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

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

CC BY-SA 3.0
2016-06-01T10:47:23.353Z
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).
Jan Špaček
CC BY-SA 3.0
2011-10-10T15:03:33.233Z
2011-10-10T15:03:33.233Z
V Vinay
<p>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.</p>

<p>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:
<a href="http://www.tau.ac.il/~nogaa/PDFS/testr4.pdf">"Regular languages are testable with a constant number of queries"</a></p>

CC BY-SA 3.0
2011-10-10T12:34:50.177Z
2011-10-10T20:28:49.567Z
2011-10-10T20:28:49.567Z
Dana Moshkovitz
<p>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:</p>

<ul>
<li>yes, the famed result is that <a href="http://lambda.uta.edu/cse5317/notes/node9.html">Deterministic Finite Automatons recognize regular languages</a> - so now you know what you need to implement regular expression matching.</li>
<li><a href="http://en.wikipedia.org/wiki/Pushdown_automata">Pushdown Automata</a> recognize <a href="http://en.wikipedia.org/wiki/Context-free_grammar">Context-Free grammars</a> - now you have an idea of what a parser looks like (or at least a large class of those).</li>
<li><a href="http://en.wikipedia.org/wiki/Tree_automaton">tree automata</a> <a href="http://tata.gforge.inria.fr/">recognize</a> statements over <a href="http://en.wikipedia.org/wiki/Monadic_second-order_logic#Syntax">monadic second-order logic</a> - now you have an idea of what it takes to implement some constraint programming languages, or ... <a href="http://www.cs.toronto.edu/~libkin/papers/tcs-icdt01.ps.gz">some statements in SQL</a>, for example.</li>
</ul>

<p>(and of course I'm skipping a lot of other classes)</p>

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

<p>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 <a href="http://en.wikipedia.org/w/index.php?title=Special%3aBookSources&amp;isbn=0201537710"><em>Foundations of Databases</em></a> by Abiteboul &amp; al, and trying to connect this back to class material. Of course it's just <em>one</em> 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.</p>

CC BY-SA 3.0
2011-10-10T07:36:31.450Z
2011-10-10T15:19:44.377Z
2011-10-10T15:19:44.377Z
Francois G
<p>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.</p>

CC BY-SA 3.0
2011-10-11T13:58:19.303Z
Welcome, Ganesh !
Suresh Venkat
CC BY-SA 3.0
2011-10-11T14:11:32.077Z
A nice way of teaching automata. Would you be willing to share  your lecture notes?
Martin Berger
CC BY-SA 3.0
2011-10-11T13:10:44.420Z
2011-10-11T13:10:44.420Z
Ganesh
<p>There has been considerable research related to automata theory in model checking used in the industry. Check <a href="http://www.fields.utoronto.ca/programs/scientific/11-12/constraint/CLS/">Moshe Vardi's recent lectures at Fields Institute</a>, in particular the 3rd lecture "Logic, Automata, Games, and Algorithms" for a taste of why automata theory is still important and useful.</p>

<blockquote>
  <p>Abstract: </p>
  
  <p>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.</p>
</blockquote>

<p>The slides and audio files of lectures are available here: <a href="http://www.fields.utoronto.ca/audio/11-12/CLS_constraint/vardi/">1</a>, <a href="http://www.fields.utoronto.ca/audio/11-12/CLS_constraint/vardi2/">2</a>, <a href="http://www.fields.utoronto.ca/audio/11-12/CLS_constraint/vardi3/">3</a>.</p>

CC BY-SA 3.0
2011-10-11T13:29:48.663Z
2011-10-11T13:29:48.663Z
Kaveh
<p>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 <em>concept</em> of the automaton is a very core one.</p>

CC BY-SA 3.0
2011-10-10T18:51:08.283Z
2011-10-10T18:51:08.283Z
Steven Stadnicki
<blockquote>
  <p>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.</p>
</blockquote>

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

CC BY-SA 3.0
2011-10-11T09:12:41.123Z
2011-10-11T09:12:41.123Z
Jeffε
<p>We should take into account the semantics of the words "practical" and "application". For some students, <em>practical</em> 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.</p>

<p>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 <em>applying</em> in your code the same <strong>conceptual ideas</strong> behind DFA minimization.</p>

<p>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 <em>applications</em> 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 <strong>structure</strong> 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.</p>

CC BY-SA 3.0
2011-10-11T00:42:38.653Z
2011-10-11T00:42:38.653Z
Janoma
<p>Thrown together with logics, automata can offer ways to check statemens like</p>

<p>$\qquad A \models \varphi$</p>

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

<p>Considering the automata side of things leads to nice algorithms. For example, if $\varphi$ is an <a href="http://en.wikipedia.org/wiki/Linear_temporal_logic">LTL</a> 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)$</p>

CC BY-SA 3.0
2011-10-10T17:07:35.743Z
2011-10-10T17:07:35.743Z
Raphael
<p>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. </p>

<p>See for example <a href="http://arxiv.org/abs/cs.LG/0406011" rel="nofollow" title="CSSR">CSSR</a>, an algorithm for blindly reconstruction hidden states; it's more efficient and flexible than Hidden Markov Models.</p>

CC BY-SA 3.0
2011-10-11T22:53:52.023Z
To add to the practial side, Hidden Markov Models are used in speech recognition programs such as Kurzweil.
tdyen
CC BY-SA 3.0
2011-10-11T20:25:36.830Z
2011-10-11T20:25:36.830Z
Elliot JJ
<p>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.</p>

CC BY-SA 3.0
2012-02-19T04:47:50.747Z
2012-02-23T08:49:42.250Z
2012-02-23T08:49:42.250Z
Sourabh
<p>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.</p>

CC BY-SA 3.0
2013-09-09T18:58:35.157Z
2013-09-09T18:58:35.157Z
Daniel
<ol>
<li><p>Ever used a tool like grep/awk/sed? Regular expressions form the heart of these tools.</p></li>
<li><p>You'll be surprised how much coding you can avoid by principled use of regular expressions - in "practical projects", like an email server.</p></li>
<li><p>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).</p></li>
<li><p>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.</p></li>
</ol>

CC BY-SA 3.0
2011-10-09T22:40:55.777Z
2011-10-09T22:40:55.777Z
Anonymous
<p>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.</p>

<p>Is automata theory still useful in practice?</p>

<p>Should it be part of undergraduate CS curriculum?</p>

CC BY-SA 3.0
2011-10-09T22:33:38.757Z
I think this is off-topic here; please see the [FAQ].
Jukka Suomela
CC BY-SA 3.0
2011-10-10T00:33:51.467Z
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.
Suresh Venkat
CC BY-SA 3.0
2011-10-10T06:40:00.267Z
I tend to agree with Suresh here, especially as automata theory is one of the stepping stones into TCS.
Dave Clarke
CC BY-SA 3.0
2011-10-10T14:27:07.520Z
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](http://cstheory.stackexchange.com/questions/6670/vertex-cover-applications-in-the-real-world), and we didn't close that question.
Peter Shor 
CC BY-SA 3.0
2011-10-10T14:39:47.270Z
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?](http://cstheory.stackexchange.com/questions/7396/what-are-regular-expressions-good-for)".
Jukka Suomela
CC BY-SA 3.0
2011-10-11T00:02:46.927Z
There is a relatively [well-known rant](http://swtch.com/~rsc/regexp/regexp1.html) from Russ Cox entitled "_Regular Expression Matching Can Be Simple And Fast (but is slow in Java, Perl, PHP, Python, Ruby, ...)_"
Hung Q. Ngo
CC BY-SA 3.0
2011-10-11T14:00:08.037Z
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.
Suresh Venkat
CC BY-SA 3.0
2013-03-06T18:35:06.037Z
see also [practical applications of FSMs](http://cs.stackexchange.com/questions/10280/practical-application-of-finite-state-machines), cs.se
vzn
CC BY-SA 4.0
2019-02-25T20:25:39.513Z
@PeterShor no, it is not on-topic. `cstheory` is for *research-level* questions, those can be discussed between two professors. This question should be moved to `cs.stackexchange.com`.
Ayrat
<soft-question><fl.formal-languages><automata-theory><teaching>
How practical is Automata Theory?
Dark Templar
# How practical is Automata Theory?

(Asked by: username_0 on 2011-10-09)

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?

**Tags:** soft-question, fl.formal-languages, automata-theory, teaching

> **Comments:**
> **username_1**: I think this is off-topic here; please see the [FAQ].  
> **username_2**: 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.  
> **username_3**: I tend to agree with Suresh here, especially as automata theory is one of the stepping stones into TCS.  
> **username_4**: 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](http://cstheory.stackexchange.com/questions/6670/vertex-cover-applications-in-the-real-world), and we didn't close that question.  
> **username_1**: 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?](http://cstheory.stackexchange.com/questions/7396/what-are-regular-expressions-good-for)".  
> **username_5**: There is a relatively [well-known rant](http://swtch.com/~rsc/regexp/regexp1.html) from Russ Cox entitled "_Regular Expression Matching Can Be Simple And Fast (but is slow in Java, Perl, PHP, Python, Ruby, ...)_"  
> **username_2**: 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.  
> **username_6**: see also [practical applications of FSMs](http://cs.stackexchange.com/questions/10280/practical-application-of-finite-state-machines), cs.se  
> **username_7**: @PeterShor no, it is not on-topic. `cstheory` is for *research-level* questions, those can be discussed between two professors. This question should be moved to `cs.stackexchange.com`.  

---

## 14 answers

### Answer by username_25 on 2011-10-09. Score: 56 | Accepted answer

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.


---

### Answer by username_8 on 2011-10-11. Score: 34

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 username_16's answer for an authoritative overview.

> **Comments:**
> **username_9**: haha, the irony  

---

### Answer by username_10 on 2011-10-10. Score: 33

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.

> **Comments:**
> **username_11**: 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).  

---

### Answer by username_12 on 2011-10-10. Score: 18

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"](http://www.tau.ac.il/~nogaa/PDFS/testr4.pdf)


---

### Answer by username_13 on 2011-10-10. Score: 16

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:

* yes, the famed result is that [Deterministic Finite Automatons recognize regular languages](http://lambda.uta.edu/cse5317/notes/node9.html) - so now you know what you need to implement regular expression matching.
* [Pushdown Automata](http://en.wikipedia.org/wiki/Pushdown_automata) recognize [Context-Free grammars](http://en.wikipedia.org/wiki/Context-free_grammar) - now you have an idea of what a parser looks like (or at least a large class of those).
* [tree automata](http://en.wikipedia.org/wiki/Tree_automaton) [recognize](http://tata.gforge.inria.fr/) statements over [monadic second-order logic](http://en.wikipedia.org/wiki/Monadic_second-order_logic#Syntax) - now you have an idea of what it takes to implement some constraint programming languages, or ... [some statements in SQL](http://www.cs.toronto.edu/~libkin/papers/tcs-icdt01.ps.gz), for example.

(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*](http://en.wikipedia.org/w/index.php?title=Special%3aBookSources&isbn=0201537710) 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.


---

### Answer by username_14 on 2011-10-11. Score: 14

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.

> **Comments:**
> **username_2**: Welcome, username_14 !  
> **username_15**: A nice way of teaching automata. Would you be willing to share  your lecture notes?  

---

### Answer by username_16 on 2011-10-11. Score: 10

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](http://www.fields.utoronto.ca/programs/scientific/11-12/constraint/CLS/), 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](http://www.fields.utoronto.ca/audio/11-12/CLS_constraint/vardi/), [2](http://www.fields.utoronto.ca/audio/11-12/CLS_constraint/vardi2/), [3](http://www.fields.utoronto.ca/audio/11-12/CLS_constraint/vardi3/).


---

### Answer by username_17 on 2011-10-10. Score: 9

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.


---

### Answer by username_18 on 2011-10-11. Score: 8

> 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


---

### Answer by username_19 on 2011-10-11. Score: 6

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.


---

### Answer by username_20 on 2011-10-10. Score: 5

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](http://en.wikipedia.org/wiki/Linear_temporal_logic) 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)$


---

### Answer by username_21 on 2011-10-11. Score: 4

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](http://arxiv.org/abs/cs.LG/0406011 "CSSR"), an algorithm for blindly reconstruction hidden states; it's more efficient and flexible than Hidden Markov Models.

> **Comments:**
> **username_22**: To add to the practial side, Hidden Markov Models are used in speech recognition programs such as Kurzweil.  

---

### Answer by username_23 on 2012-02-19. Score: 3

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.


---

### Answer by username_24 on 2013-09-09. Score: 2

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.


---

