21

I loved the course I took in Automata Theory and Formal Languages, so naturally I started looking around the interwebs to learn what happened since the time the books on which the course was based were written.

What I discovered was that the list of stuff I wasn't familiar with seemed to be very short. For example, from the list of automatons in the Wikipedia entry for the subject, half were covered by the course, and the other half were mostly related to the one language not covered by the course.

Further, when researching about the applications of the theory, I got mostly the same results: programming language syntax, compilers, text search, and.... that's about it.

So is it really that dead? Or does it continues to evolve? Are there new applications for the theory?

EpsilonVector
  • 3,973
  • 7
  • 38
  • 62
  • interesting but slightly off-topic. 5 upvotes. Really? – Mitch Wheat Jun 04 '10 at 00:51
  • 10
    Its not dead, its just resting. Pining for the fjords. – fmark Jun 04 '10 at 00:53
  • 1
    @Mitch Wheat - Maybe a ScienceOverflow is in order – Aiden Bell Jun 04 '10 at 00:56
  • @Aiden, why? its directly programming related. Probably less relevant to most of the SO population, but is as relevant as design patterns is to a certain population of programmers – Keith Nicholas Jun 04 '10 at 00:59
  • 2
    @Keith - I think you missed my point. I disagree with Mitch, and think that it is relevant. Certainly better here than anywhere else. – Aiden Bell Jun 04 '10 at 01:00
  • 1
    I think this is relevant - it's a valid theory to implement - but perhaps best as a community wiki? – mdma Jun 04 '10 at 01:01
  • 2
    @Hamish Grubijan - I will be the Jon Skeet there ;) – Aiden Bell Jun 04 '10 at 01:07
  • I think it's off-topic, as are many things taught in Computer Science classes. It has little or nothing to do with programming. It would be a good question for ComputerScienceOverflow.com, where the vast majority of SO users would ignore it. – John Saunders Jun 04 '10 at 01:07
  • 1
    The debate about whether this is related to programming notwithstanding, this question should be marked community wiki. – danben Jun 04 '10 at 01:19
  • @danben: why CW? It doesn't excuse a bad question. – John Saunders Jun 04 '10 at 01:21
  • 4
    A thought: considering the amount of enthusiasm this question generated (as implied by the upvotes), maybe there's enough interest in this to keep it open even though it is not directly programming related? Maybe I'm still under the influence of my academic surrounding, but I figure it is within reason to give the occasional nod towards the theoretical roots of our field. – EpsilonVector Jun 04 '10 at 01:32
  • 10
    It's amazing the confusion generated over whether a question about automata theory is programming or not, showing that this is a poorly understood topic. Automata are a way of modelling and solving real problems, and are as equally relevant as algorithm design, choosing the right data structure or understanding how virtual memory operates - all of which feature on SO and were also taught to me at uni - does mean they are only for academics also? – mdma Jun 04 '10 at 03:03
  • 15
    Anyone who thinks this question is off-topic should not work professionally as a programmer. – Michael Borgwardt Jun 04 '10 at 07:37
  • @EpsilonVector: which didaxtic book did you use in your course? I see that the:enthusiasm a class generates is highly dependant on the book used and lecturer – user5193682 Aug 09 '16 at 09:57

9 Answers9

19

Automatons are really useful. I completed my degree in software engineering and computer science nearly 20 years ago. One of the first courses was Models of Machines, which covered FSAs, and ventured a bit into turning machines, computability, halting problem etc.

Everyone thought the course was either boring, irrelevant, too difficult or pointless. The circles and arcs made little sense to anyone, and what's the point of a tape with just ones on it? What's wrong with a hard disk? At the end of the course, the lecturer gave out a questionnaire - how useful do you think this course will be in one month, in one year, in ten years. Then, I answered not useful for all of them. Now it would be increasing usefullness with time, ending with "very useful"

I've used automata lots in my day job, and they are the right tool for certain classes of problems, with little else to compete with it. I've used them for compressing multi-million word lists+category data (ok, quite banal), and also implemented an extension where the symbols are complex objects and the state transitions are predicates. This allowed a complex set of rules to be compiled to a deterministic FST and all rules evaluated simultaneously and deterministically with no redundant computation.

My vote is for still relevant!

mdma
  • 56,943
  • 12
  • 94
  • 128
4

Automata and formal languages are foundation of regular expressions, parsers, compilers, virtual machines, etc. which improve regularly.

There are also required in the domain of theorem prover for program checking, which aims to prove that a program or a protocol achieves what it pretends to do. This domain is critical (vote machine software, banking transaction, security systems in vehicle, etc.) and still under development.

So no, the automata theory and formal languages are not dead!

kabado
  • 343
  • 5
  • 9
3

It's not dead, more 'put out to stud' - it's a simple formalism which is used more as the basis for others, rather than being a particularly active research topic.

Henry Thompson's work on XML schemata uses and extends automata theory.

Many embedded software projects make heavy use of finite state machines, which are related to automata, and some of the techniques to work with them draw on or extend automata theory.

Pi-calculus extends automata theory with the concept of bisimulation and adds capabilities for analysing concurrent processes. It's the closest bit of recent research to the automata theory I learnt at university.

Pete Kirkham
  • 48,893
  • 5
  • 92
  • 171
1

I think as new areas of computing, such as quantum computing and hypercomputation open up then there will be new applications requirements, requirements and theoretical bredth from automata theory and things like evolutionary automata and computation, cellular automata and whatnot.

I don't think it is dead, just a bit cold for the time being.

Aiden Bell
  • 28,212
  • 4
  • 75
  • 119
1

I think Automata Theory is involved in a lot of areas without people realising. For example, I can see it's application in cryptography and cryptanalysis.

Anthony
  • 12,177
  • 9
  • 69
  • 105
0

a lot of process control stuff is heavily based on the theory. Especially in terms of proving the robustness of control systems.

Keith Nicholas
  • 43,549
  • 15
  • 93
  • 156
0

Take a look at workflow processes and see how automata theory could be put to use there in formalizing the concepts and patterns described: Workflow Patterns

Khorkrak
  • 3,911
  • 2
  • 27
  • 37
0

One of the new techniques I came across a few years ago is called Parsing Expression Grammars, aka PEGs aka Packrat Parsing. Bryan Ford has done some work on it which can be viewed at http://pdos.csail.mit.edu/~baford/packrat/.

This is basically a top-down recursive descent parser, and one of the advantages of it is that lexical analysis and semantic analysis can be performed in one step.

PEGs compare with CFGs in that PEGs are more suited to parsing a context-free language, whereas CFGs are more suited to generating a context-free language.

Umar Farooq Khawaja
  • 3,925
  • 1
  • 31
  • 52
  • 1
    I'm not entirely sure how this relates to automata, save for the fact that PEGs don't fit neatly into any formal theory. They're really a nasty, nasty construction from a mathematical point of view. Useful, but nasty. It's also worth noting two other points. First, PEGs are *not* the same as Packrat parsers (Packrat parsers are memoized, PEGs are not). Second, the one-line evaluation of CFGs against PEGs is quite subjective and a little incoherent (PEG is a parsing algorithm, CFG is a mathematical formalism). – Daniel Spiewak Jun 04 '10 at 02:06
  • "Nasty" is subjective. You should specify why they are "nasty". Packrat parsers are indeed memoized, but that is an optimization, i.e., an implementation detail. As for classifying PEGs into a bucket of some sort, if you wouldn't put them into Automata and Formal Languages, where would you put them? PEG is not an algorithm. It is a grammar, much like CFG. You are probably confusing CFGs with CFLs, which is the mathematical formalism. CFL = Context Free Language CFG = Context Free Grammar PEG = Parsing Expression Grammar – Umar Farooq Khawaja Jun 04 '10 at 02:19
  • 1
    I strongly disagree with Daniel. PEGs are a formalism. A limited and limiting, as any other formalism, but perfectly a formalism. Actually, you'd hardly find an algorithm which is not a formalism. – SK-logic Jun 04 '10 at 21:58
  • 1
    And yes, there is a well defined mapping from PEG onto an automaton. Infinite lookahead does not make it too difficult. – SK-logic Jun 04 '10 at 21:59
  • 1
    @SK-logic I'm going to call `[citation needed]` on the claimed well-defined mapping from PEG into automata theory. Clearly you can define a Turing Recognizer for the PEG acceptance problem, but to my knowledge, theorists have so far been unsuccessful to cleanly define the class of languages accepted by PEGs. As one of these aforementioned theorists, I would certainly be interested in any progress along those lines. – Daniel Spiewak Jun 06 '10 at 19:57
  • @Umar Packrat parsers accept a larger class of languages than PEGs. The leading example of this is left-recursion. Vanilla PEGs can handle some very specific forms of left-recursion. Vanilla Packrat parsers are capable of handling a much larger set of left-recursive rules, and with a little bit of trickery, they can handle any form of non-hidden left-recursion. This alone implies that memoized PEGs (Packrat parsers) are at least (and probably strictly) more powerful than vanilla PEGs. – Daniel Spiewak Jun 06 '10 at 20:00
  • @Umar And no, I'm not confusing CFGs with CFLs; I'm well aware of the differences in terms. Context-free grammars are a way of specifying context-free languages. By definition, every CFL has a corresponding CFG and vice versa. CFGs do *not* imply anything related to the algorithmic parsing of said language. Though, most parser generators will allow specification of parsers using a limited subset of context-free grammars. – Daniel Spiewak Jun 06 '10 at 20:03
0

Rather than looking at the theory as dead, instead consider that it has become so practical for applications that we've moved beyond the theory. An excellent book to consider that bridges between the theory and application is Miro Samek's "Practical Statecharts in C/C++". There is now a second edition available, which I've not read. But I found nothing lacking in the first edition; to this day I find it one of the most valuable texts I have ever read.

Brent Arias
  • 29,277
  • 40
  • 133
  • 234