有限自动机有什么用? [英] What is the use of finite automata?

问题描述

有限自动机有什么用?以及我们在计算理论中研究的所有概念.我从未见过它们的用途.

What is the use of finite automata? And all the concepts that we study in the theory of computation. I've never seen their uses yet.

推荐答案

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

They are the theoretical underpinnings of concepts widely used in computer science and programming, and understanding them helps you better understand how to use them (and what their limits are). The three basic ones you should encounter are, in increasing order of power:

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

了解这些不同计算机制的理论和局限性，可以让您更好地理解问题和程序，并更深入地思考编程.

Understanding the theory and limitations of these various computing mechanisms enable you to better understand problems and programs and think more deeply about programming.

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

There was a request-for-work published about a year ago on one of the freelance coding exchange sites asking, essentially, for a program which solved the Halting Problem. Several people responded with offers, saying they "understood the requirements" and could "start immediately". It was impossible to write a program which met the requirements. Understanding computing theory enables you to not be that bidder who demonstrates, in public, that he really doesn't understand computing (and doesn't bother to thoroughly investigate a problem before declaring understanding and making an offer).

这篇关于有限自动机有什么用?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！