theory - 有限自动机的用途是什么？

Closed. This question needs to be more focused。它当前不接受答案。












想改善这个问题吗？更新问题，使其仅通过editing this post专注于一个问题。

2年前关闭。



Improve this question





finite automata的用途是什么？以及我们在计算理论中研究的所有概念。我还从未见过它们的用途。

最佳答案

它们是在计算机科学和编程中广泛使用的概念的理论基础，对它们的理解有助于您更好地理解如何使用它们（以及它们的局限性）。您应该遇到的三个基本问题是，按功率递增的顺序排列：


有限自动机，等效于正则表达式。正则表达式在编程中广泛用于匹配字符串和提取文本。它们是使用基本字符，分组和重新描述来描述一组有效字符串的简单方法。它们可以做很多事情，但不能匹配括号的平衡集。
下推式自动机，等效于上下文无关的语法。文本/输入解析器和编译器在正则表达式不够强大时使用它们（而在学习有限自动机中学习的一件事是正则表达式不能做到，这对于知道何时编写正则表达式以及何时编写正则表达式至关重要使用更复杂的东西）。上下文无关的语法可以描述“语言”（有效字符串的集合），其中在解析字符串的某一点上的有效性不取决于其他内容。
图灵机，等同于常规计算（您可以用计算机执行的任何操作）。涵盖这些内容后，您将学到的一些知识可以使您了解计算本身的局限性。一门好的理论课程将教您有关停止问题的知识，该问题使您能够识别无法编写程序的问题。一旦确定了此类问题，便知道要停止尝试（或将其改进为可能的事情）。


了解这些各种计算机制的理论和局限性可以使您更好地理解问题和程序，并对编程进行更深入的思考。

大约一年前，在一个自由编码交换站点上发布了一份工作要求，本质上是在问一个解决暂停问题的程序。好几个人以要约回答，说他们“理解了要求”，并可能“立即开始”。编写符合要求的程序是不可能的。理解计算理论使您不必成为公开证明自己确实不了解计算的出价者（并且不愿意在宣布了解并提出要约之前就不彻底调查问题）。