theory - 有限自动机有什么用？

Question

有限自动机有什么用？以及我们在计算理论中研究的所有概念。我还没有看到它们的用途。

score 32 · Accepted Answer

它们是计算机科学和编程中广泛使用的概念的理论基础，理解它们有助于您更好地理解如何使用它们（以及它们的限制是什么）。你应该遇到的三个基本的，按权力递增的顺序：

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

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

大约一年前，在一个自由编码交换网站上发布了一份工作请求，主要是要求一个解决停机问题的程序。有几个人回应了提议，称他们“理解要求”并且可以“立即开始”。编写满足要求的程序是不可能的。了解计算理论使您不再是那个在公开场合证明他真的不了解计算的投标人（并且在宣布了解并提出要约之前不会费心彻底调查问题）。

score 4 · Accepted Answer

4

有限自动机对于通信协议和匹配字符串与正则表达式非常有用。

于 2009-10-03T20:21:09.350 回答

score 2 · Accepted Answer

自动机用于硬件和软件应用程序。请在此处阅读实施部分http://en.wikipedia.org/wiki/Finite-state_machine#Implementation

还有一个基于自动机的编程的概念。请检查此http://en.wikipedia.org/wiki/Automata-based_programming

干杯

score 2 · Accepted Answer

每个 GUI，每个工作流都可以被视为一个有限自动机。将每个页面视为由于某些事件而发生的状态和转换。在满足一系列条件之前，您可能无法进入某个页面或工作流的下一阶段。

score 2 · Accepted Answer

有限自动机例如用于解析形式语言。这意味着有限自动机在创建编译器和解释器技术时非常有用。

历史上，有限状态机表明，很多问题可以通过非常简单的自动化来解决。

score 1 · Accepted Answer

尝试参加编译器课程。您很可能会使用有限状态自动机制作编译器或解释器来实现递归下降解析器。

score 1 · Accepted Answer

例如，管理具有定义生命周期的某些对象的状态。例如：书店的订单。一个订单可以有以下状态： -ordered -payed -shipping -done

有限自动机的程序知道一种状态如何被另一种状态改变。

score 1 · Accepted Answer

有限自动机是一种状态机（SM）。通常，SM 用于解析形式语言。

您可以将许多实体用作正式语言，而不仅仅是字符。

常规语言是一种形式语言。有一些理论表明，哪种类型的 SM 更适合解析常规语言： http ://en.wikipedia.org/wiki/Regular_language

8 回答 8