Is Automata Theory dead? [closed]

Question

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?

Answer 1

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!

Answer 2

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!