2

换句话说,我为什么要学习它?我什么时候要说...哦,我需要知道下推自动机或图灵机。

我看不到材料的应用。谢谢

4

4 回答 4

4

您应该了解自动机理论,因为它将帮助您了解在给定系统中计算上的可能性。了解下推自动机和通用图灵机之间区别的人会理解为什么尝试使用正则表达式解析 HTML 是一个坏主意。不认为尝试使用 RE 解析 HTML 的人。

于 2011-10-28T16:32:03.223 回答
3

有些问题非常适合这种解决方案,其中一些是:

  • 解析器
  • 有状态系统的模拟
  • 事件驱动的问题

可能还有很多其他人。如果您开始编写具有一些特定state变量的代码,具体取决于哪些函数可以执行此操作或执行此操作,您可能会从适当的 FSA 中受益。

于 2011-10-28T16:30:59.223 回答
3

首先,我的立场是,值得学习的东西不是因为它们立即有用,而是因为它们本质上是有价值的。现代教育的一大失败在于,当学生仍然易受影响时,它无法说服他们相信这一点。

话虽如此,自动机理论既具有内在价值,又非常有用。解析文本、编译程序和计算设备的能力只能使用自动机理论给我们的东西来真正理解……而充分利用计算系统需要深入理解。自动机理论允许我们回答一些关于计算的最基本问题:我们需要哪些资源来进行计算?有了给定的资源,我们能解决什么问题?有没有资源再多也解决不了的问题?更不用说复杂性理论 - 处理计算效率 - 需要自动机理论才能被有意义地定义。

于 2011-10-28T17:06:02.710 回答
0

学习自动机(只不过是机器)可以了解计算的极限。当自动机不接受字符串时,这意味着机器无法将该字符串作为输入。状态图通常给出了输入的可能结果,这使我们构建解析器/机器。

一个很好的例子是检查 email-id 的格式。如果电子邮件格式不好,软件在填写表格时不接受电子邮件 ID。在这里,该软件仅接受特定格式的电子邮件 ID。我们能够通过使用自动机和状态机在理论上对其进行分类来构建这样的软件。

于 2015-01-24T22:23:46.757 回答