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

Question

关闭。这个问题需要更多focused .它目前不接受答案。












想改善这个问题吗？更新问题，使其仅关注一个问题 editing this post .

3年前关闭。




Improve this question




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

Answer 1

它们是计算机科学和编程中广泛使用的概念的理论基础，理解它们可以帮助您更好地理解如何使用它们(以及它们的限制是什么)。您应该遇到的三个基本问题是，按功率递增的顺序:

有限自动机，相当于正则表达式。正则表达式在编程中广泛用于匹配字符串和提取文本。它们是使用基本字符、分组和重复描述一组有效字符串的简单方法。它们可以做很多事情，但它们无法匹配平衡的括号集。

下推自动机，相当于上下文无关文法。当正则表达式不够强大时，文本/输入解析器和编译器会使用它们(你在学习有限自动机时学到的一件事是正则表达式不能做的事情，这对于知道何时编写正则表达式以及何时编写正则表达式至关重要使用更复杂的东西)。上下文无关文法可以描述“语言”(有效字符串的集合)，其中在解析字符串的某个点的有效性不依赖于已经看到的其他内容。

图灵机，相当于一般计算(你可以用计算机做的任何事情)。当您涵盖这些内容时，您学到的一些内容使您能够了解计算本身的局限性。一门好的理论类(class)将教您有关停机问题的知识，它使您能够识别无法编写程序的问题。一旦你确定了这样的问题，那么你就知道停止尝试(或将其改进为可能的事情)。

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

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