自动机理论死了吗？
我喜欢我所学的自动机理论和形式语言课程，所以很自然地我开始浏览互联网，了解自该课程所依据的书籍撰写以来发生的事情。
我发现我不熟悉的东西清单似乎很短。例如，从该主题的维基百科条目中的自动机列表来看，一半是课程涵盖的，另一半主要与课程未涵盖的一种语言相关。
此外，在研究该理论的应用时，我得到了大部分相同的结果：编程语言语法、编译器、文本搜索，以及……仅此而已。
那么它真的就这么死了吗？还是继续发展？该理论有新的应用吗？
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?
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（9）
自动机真的很有用。近 20 年前，我完成了软件工程和计算机科学学位。第一批课程之一是机器模型，涵盖 FSA，并涉足车床、可计算性、停机问题等。
每个人都认为这门课程要么无聊、无关紧要、太难，要么毫无意义。圆圈和弧线对任何人来说都没有什么意义，而只有这些圆圈和弧线的磁带有什么意义呢？硬盘出了什么问题？课程结束时，讲师给出了一份调查问卷——你认为这门课程在一个月、一年、十年后有多大用处。然后，我回答对他们所有人都没有用。现在它的实用性会随着时间的推移而增加，以“非常有用”结束，
我在日常工作中大量使用了自动机，它们是解决某些类别问题的正确工具，几乎没有其他工具可以与之竞争。我使用它们来压缩数百万个单词列表+类别数据（好吧，相当平庸），并且还实现了一个扩展，其中符号是复杂对象，状态转换是谓词。这允许将一组复杂的规则编译为确定性 FST，并且所有规则同时确定性地评估，没有冗余计算。
我的投票仍然相关！
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!
自动机和形式语言是正则表达式、解析器、编译器、虚拟机等的基础，并定期改进。
在定理证明领域还需要进行程序检查，其目的是证明程序或协议实现了它假装要做的事情。该领域至关重要（投票机软件、银行交易、车辆安全系统等）并且仍在开发中。
所以不，自动机理论和形式语言还没有消亡！
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!
它并没有消亡，而是更多地“被淘汰”——它是一种简单的形式主义，更多地用作其他形式主义的基础，而不是一个特别活跃的研究主题。
Henry Thompson 在 XML 模式方面的工作使用并扩展了自动机理论。
许多嵌入式软件项目大量使用与自动机相关的有限状态机，并且一些使用它们的技术借鉴或扩展了自动机理论。
Pi 演算使用互模拟的概念扩展了自动机理论，并添加了分析并发过程的功能。这是最近与我在大学学到的自动机理论最接近的研究。
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.
我认为，随着新的计算领域，例如量子计算和超级计算的开放，那么将会有新的应用需求、来自自动机理论的要求和理论渊源，以及诸如进化自动机和计算、元胞自动机等等。
我不认为它已经死了，暂时只是有点冷。
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.
我认为自动机理论涉及到很多人们没有意识到的领域。例如，我可以看到它在密码学和密码分析中的应用。
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.
许多过程控制的内容很大程度上基于该理论。特别是在证明控制系统的鲁棒性方面。
a lot of process control stuff is heavily based on the theory. Especially in terms of proving the robustness of control systems.
看一下工作流程，看看如何使用自动机理论来形式化所描述的概念和模式：工作流程模式
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
几年前我遇到的一项新技术称为解析表达式语法，又名 PEG，又名 Packrat 解析。 Bryan Ford 对此做了一些工作，可以在 http://pdos.csail 查看.mit.edu/~baford/packrat/。
这基本上是一种自上而下的递归下降解析器，其优点之一是可以一步执行词法分析和语义分析。
PEG 与 CFG 相比，PEG 更适合解析上下文无关语言，而 CFG 更适合生成上下文无关语言。
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.
不要认为这个理论已经死了，而是认为它对于应用来说已经变得如此实用，以至于我们已经超越了理论。 Miro Samek 的《Practical Statecharts in C 是一本很好的书，可以考虑理论和应用之间的桥梁/C++”。现在有第二版，我还没有读过。但我发现第一版没有什么缺失；直到今天，我发现它是我读过的最有价值的文本之一。
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.