乔姆斯基层次结构中指定的 4 种语法的要点是什么？
What is the point of the 4 grammars specified in Chomsky hierarchy?
我目前正在研究编译器，并且正在研究“乔姆斯基层次结构和 4 种语言”这一主题。但这一切的实际目的是什么？
如果我能看到 4 种语法的真实示例，那就太好了：Unrestricted、CSG、CFG、Regular Grammer。
我在网上发现乔姆斯基层次结构连同 4 种语法用于评估认知科学中的提案，但这让我难以理解。如果有人能帮我分解一下就太好了，非常感谢！
没有实用价值。这就是重点。
让我试着分解一下。记住乔姆斯基是一位语言学家——研究人类语言的人——并且他在 1950 年代后期写作，当时计算理论不像今天这样 well-developed，这一点很有用。 （委婉地说。）他的目标是找到一个数学模型，可以为人类生成和理解句子的机制提供一些见解，他以一个特定的简单句子生成模型为出发点。
在此模型中，语法是一个函数 F，它将元素从某个字母表的任意符号序列转换为同一字母表的另一个符号序列。 F 由一组有限的对定义（称为 productions）α → β。然后我们说 F(ω) = F(ζ) 如果 F 的定义包含一些对 α → β 这样 α 是 ω 和 [=17 的子串=] 是将 ω 中的 α 的单个实例替换为 β.
的结果
这本身并不是很有趣；我们通过从一些指定的起始序列开始将其变成完整的语言，通常表示为单个符号 S，并根据需要重复应用 F 多次。 （在所有有趣的文法中，这样构造的集合是无限的，所以实际上无法构造它。但是我们可以想象从起点开始，直到找到我们想要生成的句子。）
这个模型的问题是它可以用来描述任意的图灵机。或者，如果您愿意，可以使用任意计算机程序，尽管使用图灵机更容易看出等价性。换句话说，至少在理论上可以构建一个有限语法，该语法将识别由图灵机（即用某种编程语言编写的程序）的描述组成的字符串，然后是输入和输出 仅当 应用于输入的图灵机才会产生输出。换句话说，存在（在数学意义上）这种形式的语法，在计算上等同于通用计算机。
不幸的是，如果我们的目标是理解句子，那实际上并不是很有用，因为实际上没有 运行ning 计算机倒退的算法。作为一般解决方案，我们能做的最好的事情是枚举所有可能的输入和每个输入的 运行 程序，直到找到我们希望的输出。这实际上行不通，因为程序产生输出可能花费的时间没有限制，甚至无法知道程序是否最终会结束。 （这被称为“停止问题”。）所以我们可能会卡在某些可能的输入上，而我们永远不会知道是否有其他输入可能产生了所需的输出。
因此，我们无法判断提供的输入是否“合乎语法”，即是否符合提供的语法。这不仅仅是我们为模拟图灵机而构建的特定语法的情况。这意味着我们没有信心可以从任意语法中识别句子，即使我们偶然发现了答案，我们也无法限制到达那里可能需要多少时间。
显然，这不是人类相互理解的方式。所以如果要服务于实际目的，我们必须以某种方式限制可能的文法，使它们在计算上可行。
另一方面，关于 finite-state 机器的知识很多。 finite-state 机器是没有磁带的图灵机；也就是说，它只是状态的有限集合。在每个状态中，机器读取一个输入符号并使用它来决定下一个状态。事实证明，finite-state 机器可以使用仅限于非常简单的产生式的语法（如上所述）建模，每个产生式都是 A → a B 或 A → a 形式，其中 a 是来自“终端字母表”（即单词）的符号，A 和 B 是单个语法符号。这些语法称为“正则语法”，它们在计算上等同于数学家所说的“正则表达式”（这是“正则表达式”库识别的一小部分，但那是另一个讨论）。
常规语法很容易解析。所需要的只是通过状态机进行跟踪，因此可以在不与输入长度成比例的时间回溯的情况下完成。但是常规语法太弱了，无法表示人类语言，甚至无法表示大多数计算机语言。举个简单的例子，带括号的代数表达式无法用正则文法（或 finite-state 机器）识别，因为无法计算括号的深度； finite-state 机器根本没有内存（其他 t知道它处于哪个状态，并且只有有限数量的状态）。
因此，不受限制的语法太强大而无法解析，而常规语法太弱而无法使用。 （对于复杂的解析问题很有用，即。正则表达式有一定的应用，但解析完整的计算机程序不是其中之一。）
然后，下一步是尝试找到对语法的限制，该限制仍然足够强大以表示人类语言，而又不会强大到无法进行解析。
最后，这就是乔姆斯基等级制度的起源。在上述两个极端（0 型和 3 型文法）之间，乔姆斯基提出了两个可能的中间限制——1 型和 2 型文法——并证明了它们各自的一些重要属性。
虽然这项工作被证明是形式语言理论发展的基础，但不能说它真的回答了乔姆斯基一开始提出的问题。类型 2 文法——context-free 文法——确实在计算上易于处理；它们可以在多项式时间内用简单的算法进行解析，并且可以表示大量有用的语言。但它们仍然太弱，无法代表人类语言。特别是，context-free 语法不能表示像“包含同一子字符串的两个实例的所有字符串”这样简单的语言。类型 1 文法——context-sensitive 文法——可能可以表示任何有用的语言，并且不像无限制文法那样不守规矩，但它们仍然太强大而无法解析。 （由于 context-sensitive 文法中的推导步骤永远不会变短，因此可以从起点开始按长度顺序枚举所有可能的推导，这意味着您可以判断一个句子是否由没有 运行进入停机问题。但这已经很好了；该过程需要指数级时间并且对于 non-trivial 输入来说是不可行的。）
自从乔姆斯基发表他的开创性论文以来的六十年里，人们做了大量工作来尝试在类型 1 和类型 2 语法之间找到有用的中间限制。并且对解析 context-free 语言的算法进行了大量有用的研究，这在构建编译器方面具有巨大的实用性。所有这一切都建立在乔姆斯基和其他计算理论家所做的重要工作的基础上，这些理论家的工作是他建立的基础——马尔可夫、图灵、丘奇和克莱恩，仅举几例值得研究的例子。但乔姆斯基最初的计划仍未解决。
因此，如果您的目标是为一种编程语言构建一个简单的解析器，乔姆斯基层次结构可能只是一个有趣的注脚。但是如果你对形式语言理论的学术研究感兴趣，还有很多有趣的未解决问题需要研究。
我目前正在研究编译器，并且正在研究“乔姆斯基层次结构和 4 种语言”这一主题。但这一切的实际目的是什么？
如果我能看到 4 种语法的真实示例，那就太好了：Unrestricted、CSG、CFG、Regular Grammer。
我在网上发现乔姆斯基层次结构连同 4 种语法用于评估认知科学中的提案，但这让我难以理解。如果有人能帮我分解一下就太好了，非常感谢！
没有实用价值。这就是重点。
让我试着分解一下。记住乔姆斯基是一位语言学家——研究人类语言的人——并且他在 1950 年代后期写作，当时计算理论不像今天这样 well-developed，这一点很有用。 （委婉地说。）他的目标是找到一个数学模型，可以为人类生成和理解句子的机制提供一些见解，他以一个特定的简单句子生成模型为出发点。
在此模型中，语法是一个函数 F，它将元素从某个字母表的任意符号序列转换为同一字母表的另一个符号序列。 F 由一组有限的对定义（称为 productions）α → β。然后我们说 F(ω) = F(ζ) 如果 F 的定义包含一些对 α → β 这样 α 是 ω 和 [=17 的子串=] 是将 ω 中的 α 的单个实例替换为 β.
这本身并不是很有趣；我们通过从一些指定的起始序列开始将其变成完整的语言，通常表示为单个符号 S，并根据需要重复应用 F 多次。 （在所有有趣的文法中，这样构造的集合是无限的，所以实际上无法构造它。但是我们可以想象从起点开始，直到找到我们想要生成的句子。）
这个模型的问题是它可以用来描述任意的图灵机。或者，如果您愿意，可以使用任意计算机程序，尽管使用图灵机更容易看出等价性。换句话说，至少在理论上可以构建一个有限语法，该语法将识别由图灵机（即用某种编程语言编写的程序）的描述组成的字符串，然后是输入和输出 仅当 应用于输入的图灵机才会产生输出。换句话说，存在（在数学意义上）这种形式的语法，在计算上等同于通用计算机。
不幸的是，如果我们的目标是理解句子，那实际上并不是很有用，因为实际上没有 运行ning 计算机倒退的算法。作为一般解决方案，我们能做的最好的事情是枚举所有可能的输入和每个输入的 运行 程序，直到找到我们希望的输出。这实际上行不通，因为程序产生输出可能花费的时间没有限制，甚至无法知道程序是否最终会结束。 （这被称为“停止问题”。）所以我们可能会卡在某些可能的输入上，而我们永远不会知道是否有其他输入可能产生了所需的输出。
因此，我们无法判断提供的输入是否“合乎语法”，即是否符合提供的语法。这不仅仅是我们为模拟图灵机而构建的特定语法的情况。这意味着我们没有信心可以从任意语法中识别句子，即使我们偶然发现了答案，我们也无法限制到达那里可能需要多少时间。
显然，这不是人类相互理解的方式。所以如果要服务于实际目的，我们必须以某种方式限制可能的文法，使它们在计算上可行。
另一方面，关于 finite-state 机器的知识很多。 finite-state 机器是没有磁带的图灵机；也就是说，它只是状态的有限集合。在每个状态中，机器读取一个输入符号并使用它来决定下一个状态。事实证明，finite-state 机器可以使用仅限于非常简单的产生式的语法（如上所述）建模，每个产生式都是 A → a B 或 A → a 形式，其中 a 是来自“终端字母表”（即单词）的符号，A 和 B 是单个语法符号。这些语法称为“正则语法”，它们在计算上等同于数学家所说的“正则表达式”（这是“正则表达式”库识别的一小部分，但那是另一个讨论）。
常规语法很容易解析。所需要的只是通过状态机进行跟踪，因此可以在不与输入长度成比例的时间回溯的情况下完成。但是常规语法太弱了，无法表示人类语言，甚至无法表示大多数计算机语言。举个简单的例子，带括号的代数表达式无法用正则文法（或 finite-state 机器）识别，因为无法计算括号的深度； finite-state 机器根本没有内存（其他 t知道它处于哪个状态，并且只有有限数量的状态）。
因此，不受限制的语法太强大而无法解析，而常规语法太弱而无法使用。 （对于复杂的解析问题很有用，即。正则表达式有一定的应用，但解析完整的计算机程序不是其中之一。）
然后，下一步是尝试找到对语法的限制，该限制仍然足够强大以表示人类语言，而又不会强大到无法进行解析。
最后，这就是乔姆斯基等级制度的起源。在上述两个极端（0 型和 3 型文法）之间，乔姆斯基提出了两个可能的中间限制——1 型和 2 型文法——并证明了它们各自的一些重要属性。
虽然这项工作被证明是形式语言理论发展的基础，但不能说它真的回答了乔姆斯基一开始提出的问题。类型 2 文法——context-free 文法——确实在计算上易于处理；它们可以在多项式时间内用简单的算法进行解析，并且可以表示大量有用的语言。但它们仍然太弱，无法代表人类语言。特别是，context-free 语法不能表示像“包含同一子字符串的两个实例的所有字符串”这样简单的语言。类型 1 文法——context-sensitive 文法——可能可以表示任何有用的语言，并且不像无限制文法那样不守规矩，但它们仍然太强大而无法解析。 （由于 context-sensitive 文法中的推导步骤永远不会变短，因此可以从起点开始按长度顺序枚举所有可能的推导，这意味着您可以判断一个句子是否由没有 运行进入停机问题。但这已经很好了；该过程需要指数级时间并且对于 non-trivial 输入来说是不可行的。）
自从乔姆斯基发表他的开创性论文以来的六十年里，人们做了大量工作来尝试在类型 1 和类型 2 语法之间找到有用的中间限制。并且对解析 context-free 语言的算法进行了大量有用的研究，这在构建编译器方面具有巨大的实用性。所有这一切都建立在乔姆斯基和其他计算理论家所做的重要工作的基础上，这些理论家的工作是他建立的基础——马尔可夫、图灵、丘奇和克莱恩，仅举几例值得研究的例子。但乔姆斯基最初的计划仍未解决。
因此，如果您的目标是为一种编程语言构建一个简单的解析器，乔姆斯基层次结构可能只是一个有趣的注脚。但是如果你对形式语言理论的学术研究感兴趣，还有很多有趣的未解决问题需要研究。