10

我目前正在学习离散数学测试，我们正在学习乔姆斯基的层次结构和识别层次结构每个级别的自动机类型。我被告知大多数计算机语言都属于层次结构的“第 2 级和第 1 级”，但不准确。

我的问题是：

  1. 每个级别都有哪些功能？

  2. 这仅仅是理论基础吗？我想知道像 Dennis Ritchie 和 James Gosling 这样的语言设计师在设计 C 和 Java 时是否必须考虑到这一点。他们有吗？有人会如何应用这个？

  3. 我们被告知图灵机可以识别层次结构的第 0 级。如果有，是否有属于 0 级的语言特征？我猜这可能是自然语言处理，是吗？

4

2 回答 2

7

  1. 没有任何。1级包括2级。也许我误解了你，所以要完整：

    • 正则语言在正则表达式匹配中使用。口语：DFA 不能算。如果要匹配括号，则需要计数。[3级]
    • 语言语法通常是上下文无关语言。见 2) [2 级]
    • 上下文相关语言仅在理论上使用。见 3) [1 级]

  2. 它有助于设计词法分析器和解析器。我不知道 C 的创建者是否考虑过这一点，但 Java 是肯定的。解析器生成器

  3. 图灵机计算任何可以计算的东西。“可以计算”甚至被定义为：可以被图灵机接受。这当然包括自然语言处理。2 级以上的任何东西对于语言生成都不是很有用，因为读取此类输入的程序可能不会停止（无法再解决单词问题）。

于 2009-06-14T15:33:49.163 回答
4

类型 3 语法生成常规语言。这些语言具有以“xxx”开头、包含“xxx”、以“xxx”结尾、包含奇数个 y 等特征的语言。有限自动机（确定性或非确定性）识别这些语言。

类型 2 语法生成上下文无关语言。这些语言具有一些特征，例如某些数量的 x 后跟更少、或更多或相等数量的 y，或者一个单词后跟同一个单词，但相反。下推自动机识别这些语言......想想带有堆栈的有限自动机。

类型 1 语法生成上下文相关的语言。这些语法非常接近 0 型语法，因此通常很难找到它们之间的区别。LBA（线性有界自动机）识别这些语言，想想资源有限的图灵机……想想现代计算机。

0 型语法生成图灵语言，有时称为递归可枚举语言。这些基本上是您可以编写计算机程序来识别的任何语言，但它们确实与类型 1 融合在一起，因为真正的计算机通常具有某种内存限制。

有限自动机和下推自动机对于解决编写编译器时出现的问题非常重要。然而，这不是你研究它们的原因，你研究它们是为了了解可以/不能计算的限制。许多程序员认为你可以用电脑解决任何问题。可计算性理论教你其他方面。

由“Dude”编辑 - 好的，这是一个易于理解（且著名）的问题，任何图灵机、计算机、程序员或外星天才都无法解决......

想象一下，您有一些多米诺骨牌……但不是点状图案，而是顶部和底部有一些简短的单词，例如“aba”和“cab”之类的单词。如果我给你 5 或 10 或 50 块这样的多米诺骨牌，你能把它们排列成顶部的单词，全部连接在一起，与底部的连接单词完全匹配。您可以制作任意数量的多米诺骨牌副本。

多米诺骨牌示例（人为:) (a/aab), (aba/ac), (cab/ab) 是一组 3 块多米诺骨牌，其中顶部 (a+aba+cab) 正好等于底部 (aab+ac+ab) .

这听起来很容易，但通常无法解决。

顺便说一句，当我第一次阅读/理解这个问题时......我在想......哦，哦！开始看起来不错！

于 2009-06-14T15:48:56.583 回答