问题标签 [chomsky-hierarchy]

我看到在这种语言中，当我们决定 m=n; 那么我们就没有b了；所以我们不能用 c's 来比较它们。所以，我认为它不应该是 CFL。

但下面的解决方案表明它是 CFL

在上面给出的解决方案中，L2 CFL 是否正确？

如何将常规语法转换为有限自动机（FA）？例如，对应于以下常规语法的有限自动机会是什么样子？

我试图通过使用一些真实语言作为模型来理解乔姆斯基层次结构的四个层次。他认为所有自然语言都可以通过上下文无关文法生成，但席伯反驳了这一理论，证明瑞士德语等语言只能通过上下文相关文法生成。由于乔姆斯基来自美国，我猜美国语言是上下文无关语法的一个例子。我的问题是：

1. 是否有可以通过常规语法（类型 3）生成的语言？
2. 既然递归可枚举语法可以生成所有语言，为什么不使用它呢？它们是否过于复杂且线性度较低？
3. 瑞士德语有什么特点，无法通过上下文无关语法生成？

我问这个问题是因为我偶然发现了乔姆斯基语言类型的公认答案

这句话指的是 Type-0 语法：

这意味着如果你有一种比这种类型更具表现力的语言（例如英语），你就不能编写一个算法来列出该语言的每一个（并且只有这些）单词

据我所知：

• 英语是什么没有数学描述，因此争论它在形式语言层次结构中的位置是没有意义的。
• 如果有，那么英语肯定会被一些 Type-0 语法识别，因为它是由有限数量的推理定义的——它可以是公理、语法等等。（如果不是——如果不是通过有限的步骤，别人怎么能定义它？）

因此：

• 我们不能开始谈论语法需要多么“富有表现力”才能精确地生成一个未知的数学对象

因此我的问题：

• 如何定义一种不符合乔姆斯基层次结构的语言？
• 如果（？）数学家需要有限数量的步骤来定义具有不使它们递归可枚举的基数的集合 - 那么必须存在比 Type-0 更具表现力的文法，因为它们（数学家）遵循有限数量的规则（生产规则，如果你愿意的话）生产一个非 RE 集。他们在哪？

GATE 2008 论文中提出了以下问题：

如果 L 和 L' （L 补码）是递归可枚举的，那么 L 是 ?

a) 常规
b) CFL
c) CSL
d) 递归

正确的选项是选项 (d)，我接受这是真的。但我的问题是为什么不能是常规的或 CSL ？

因为我认为如果我们认为L是正则的，那么L'也是正则的（因为正则语言在互补下是封闭的）。现在因为L'是规则的，所以根据'乔姆斯基层次结构' L'也是递归可枚举的。即使L在常规之后，它也适合问题陈述，那么为什么选项（a）不是正确的选项？CSL 也是如此，那么为什么选项 (c) 也不是正确的选项？

我正在写一篇关于Robot Framework的论文。我想包括一个关于乔姆斯基层次结构的部分，并描述它属于哪个层次结构。据我所知，大多数编程语言都可以用 CFG（上下文无关语法）来描述，但不是其中的一部分（例如，检查变量是否在 C 或多级括号中定义）。我的问题是是否可以在 CFG 中描述 Robot Framework -> 可以使用非确定性下推自动机进行检查。我认为它可以通过其语法的类似表格的格式来实现。

我实际上不明白如何将 scfg 转换为 cnf。我知道如何转换cfg。我应该如何处理概率？

例子：

我也在寻找有关预测二级 RNA 结构的任何信息（完美的一些代码示例）。我会很高兴得到帮助！

我目前正在研究编译器，主题是“乔姆斯基层次结构和 4 种语言”。但它让我不知道这一切的实际目的是什么？

如果我能看到 4 种语法的真实示例，那就太好了：Unrestricted、CSG、CFG、Regular Grammer。

我在网上发现，乔姆斯基层次结构和 4 种语法被用来评估认知科学中的建议，但这超出了我的想象。如果有人能帮我分解一下，那就太好了，非常感谢！

最近我注意到大多数编程语言的正则表达式引擎并不是形式语言理论意义上的正则表达式的忠实实现。前瞻和后瞻等特性支持上下文无关文法的匹配，这是常规文法的超集。

然而，更有趣的是，许多正则表达式引擎可以匹配某些上下文相关的语言。本文提供了一些示例：https ://www.npopov.com/2012/06/15/The-true-power-of-regular-expressions.html#context-sensitive-grammars

作者质疑 PCRE 是否可以匹配所有上下文相关的语言，而不仅仅是其中的一些。任何人都可以对此有所了解（最好通过正式证明）？