问题标签 [chomsky-hierarchy]

我有这个语法：

G = (N, Epsilon, P, S)

和

为什么这是一个只有 0 类型的文法？

我认为是因为aA -> aaaA，但我看不出它与规则有何冲突。

规则必须像这样构建：

x1 A x2 -> x1 B x2 尽管：

A是N的元素；

x1,x2 是 V* 的元素；

B是VV*的元素；

，我在V = N united Epsilon这里看不到问题。

a 来自 V，A 来自 N，而 A 的右边可能有空词，它也是 V* 的一部分，所以左边就可以了。

右边又是x1，是a，那么我们可以说aaA是VV*的一部分，aa是V，A是V*，而右边是x2，所以又是空的。

我试图理解不同层次的乔姆斯基层次结构。

我检查了一些例子，这是一个我不太明白的例子。也许有人知道为什么这不是一种上下文相关的语言：

目前我正在努力学习和理解正式的语言和语法。我了解乔姆斯基层次结构，但我发现了一项我不知道他们如何获得解决方案的任务。任务是：

1. 这个语法的最大类型是什么？
2. 最大的类型是L(G)什么？

我知道语法是类型 2，但在答案中写的L(G)是类型 3。

似乎也有描述这种语言的第 3 类语法，但是你怎么知道哪种是形式语言的最大类型呢？有什么诀窍吗？

大多数编程语言的词法语法是相当不具表现力的，以便快速对其进行词法分析。我不确定 Rust 的词法语法属于哪个类别。其中大部分似乎是常规的，可能除了原始字符串文字：

哪个打印：

由于我们可以任意添加许多#，所以它似乎不能是规则的，对吧？但是语法至少是上下文无关的吗？或者关于 Rust 的词汇语法是否有一些与上下文无关的东西？

有关的：Rust 的句法语法是上下文无关的还是上下文敏感的？

几乎没有任何编程语言的句法语法是规则的，因为它们允许任意深度嵌套的括号。Rust 也可以：

但是，Rust 的句法语法至少是上下文无关的吗？如果不是，什么元素使语法上下文敏感？或者语法甚至可以递归枚举，就像C++ 的句法语法一样？

相关：Rust 的词法语法是规则的、上下文无关的还是上下文敏感的？

所以我知道基本的 4 步方法。删除 epsilon，然后是小于 2 的变量，依此类推。但是，对于我们在测试中必须做的问题，这种方式花费的时间太长了。

这是一个示例：
将此上下文无关文法转换为等效的乔姆斯基范式文法。请记住从语法中删除所有无用的符号。

S → 大旭 | STUVWXY
T → UU | abc
U → bSc | ε
V → aV | Wb
W → cW | Va
X → bT | Tc
Y → cba | ε

这是考试 6 个问题中的 1 个。我们有 50 分钟的时间来完成整个测试。我可以做到这一点，但每次大约需要 30-40 分钟。有没有人知道任何技巧或捷径可以让这样的事情变得更快？

谢谢。

由于递归可枚举语法不受限制，是否可以在 LHS 中有一个或多个终端（即没有非终端）的产生式？

在我的计算机科学入门课程中，我们正在学习乔姆斯基层次结构。我的教授多次提到 lrk 语法，但书中没有教授它们。据我了解，它们是生成明确语言的确定性上下文无关语法的子集。但它们与确定性 CFG 有何不同？

这是我们在课堂上使用识别相关语法的设备所学习的乔姆斯基层次结构：

在单独的说明中（如果这个问题应该是单独的帖子，请在评论中告诉我） - 线性有界非确定性图灵机与决策者有何不同？

查看Chomsky 语法层次结构，我发现对于类型 2 语法（上下文无关语法），存在非常好的工具来帮助创建软件以将这些从文本读取到内存中可用的数据结构中。根据我的经验， Antlr4是执行此操作的工具之一。

最近我遇到了 Markdown，它原来是一种上下文相关的语法（即 Chomsky 类型 1），因此不存在Antlr4的语法定义。见这里和这里。

所以我想知道；

• 是否有工具可以帮助创建上下文相关语法的解析器？
• 如果没有，这样的事情甚至可能吗？

Java 是否位于 Chomsky Hierarchy 的 Type-0 lavel 中？

据我所知，C++ 模板是图灵完备的，所以 C++ 位于 Chomsky Hierarchy 的 Type-0 中。Java也有Generic，Java是否位于Chomsky Hierarchy的Type-0 lavel？