DFA、NFA、PDA和图灵机的现实世界应用

Question

我现在正在学习计算理论课程，我能够很好地理解其中的概念，并且能够解决问题。当我询问我的导师关于实际应用时，他告诉我这些概念在编译器设计中肯定会有用且必不可少。但是，为了进行有意义的学习，我需要一些关于如何在编码中使用这些概念的解释。

例如，如果我想设计自己的grep，我将使用C语言中的字符串函数。我不知道如何在编码中使用正则表达式。

同样的情况也适用于图灵机。

如果我想要加两个数字，为什么我必须按照那些一元概念去做呢？硬件是否实现了这些概念？

- Muthu Ganapathy Nathan

Answer 1

这篇文章实际上讨论了DFA和NFA在高效正则表达式匹配中的应用，并详细介绍了哪些真实库使用了高效的Thompson NFA方法。

图灵机主要作为计算机定义的实用工具。如果有人告诉我一门新语言，我可以尝试在其中构建图灵机来检查它是否像C或Java一样强大（不要与易用性混淆）。

- Matthew Flaschen

---

尝试在其中构建图灵机。你能解释一下吗？（这是否类似于尝试编写一个获取100000之间所有质数的代码，即通过编写示例代码来检查强大性的方法？）因此，仅出于这个目的，才会使用图灵机？感谢提供链接，它非常有用。 - Muthu Ganapathy Nathan

获取这些质数只是一个孤立的测试。如果我能制造出图灵机（维基百科有一个很好的概述），我就可以找到这些质数，以及解决任何其他可计算问题。 - Matthew Flaschen

假设丘奇-图灵论题。;D - Patrick87

@Patrick87，不用担心。如果我们发现某些问题图灵机无法计算，我们只需说它不是“有效可计算的”。;) - Matthew Flaschen

Answer 2

NFA和DFA：这两种方法用于编译器中从源文件的字符中创建标记并将其返回给语法分析器。您可以从UNIX的lex和yacc手册了解更多信息。

图灵机：我认为它没有与其原始学术目的不同的用途。

- luis

---

关于“图灵机”：为什么要使用图灵机？它是如何发明的？或者为什么会出现这些概念？ - Muthu Ganapathy Nathan

为了定义何为可计算或不可计算，艾伦·图灵首先需要创建一种能够计算所有可计算事物的抽象机器。这就是图灵机的起源。如果这个抽象机器无法解决问题，那么该问题就是不可解的。更多信息可以在原始论文《关于可计算数及判定问题的应用》中找到。请注意，这不是唯一的相关工作。阿隆佐·丘奇的 Lambda Calculus 也解决了可计算性问题。 - luis

为了补充Luis的评论：图灵机被引入以系统地研究计算本身的性质，从而定义了可计算性的概念。 - Cyriac Antony