问题标签 [chomsky-normal-form]

我正在尝试学习CYK 解析算法。

对于这组语法规则，结果表对于给定的两个句子是否正确？

我试图证明以下几点：

如果 G 是乔姆斯基范式中的上下文无关文法，那么对于任何字符串 w 属于长度为 n ≥ 1 的 L(G)，它恰好需要 2n-1 步来对 w 进行任何推导。

我将如何证明这一点？

我需要你尽快的帮助。我应该转换为乔姆斯基范式。

我尝试过很少，但我总是卡住，因为我有这些混合部件，例如 110Y ......

目标是将伪代码转换为实际的工作代码。我以为我已经大致弄清楚了，但有些地方不太对劲。

我使用的规则是

这是伪代码：

这是实际的代码：

我得到：

但是，正如您所知，baba 可以从该语法派生而来。

我只是在语法的一部分上遇到了问题：

删除 epsilon 产品后，我得到：

我很困惑这是否正确。在文法中，B 也是一个可为空的变量。我是否还必须在后一种语法中包含 CA 和/或 A？

任何帮助表示赞赏。

我有以下 CFG 规则：

• S -> BSA | ε
• A -> abC | 一个 | C
• B -> baC | 乙 | ε
• C -> 抄送 | AB | ε

我处于算法的 epsilon 消除阶段，我已经消除了以下 epsilon C -> epsiolon，B -> epsilon，这是我到目前为止得到的：

• S_0 -> S
• S -> BSA | 南非 | ε
• A -> abC | 一个 | c| 抗体
• B -> baC | 乙 | 巴
• C -> 抄送 | AB | 交流| A 由于 S 是原始起始变量，我是否还应该消除 S-> epsilon（以粗体显示）？

我还应该在算法的单元规则阶段将 epsilon 复制到 S_0 吗？

我已经实现了 cyk 算法来检查一个字符串，它是否在使用 java 以 CNF 形式给出的语法中。所以如果我考虑以下是语法，

然后我可以验证像 abba 这样的字符串。但现在我有一个语法如下，采用 BNF 形式

我需要将其转换为 CNF 形式。而且我已经搜索并发现应该执行以下操作以将任何 CFG 转换为 cnf 形式。1.删​​除空值，然后删除单位产品。但是他们展示的示例是针对以下语法的，

但是在 BNF 形式中有很多其他的语法，我不知道如何转换它。并且也很难识别上述 BNF 语法的终端。谁能解释一下程序，这样我就可以继续了。提前致谢

在这个旧的考试问题中，我需要将语法转换为 CNF，但我怀疑提供的解决方案是错误的。

语法：

在第一步中，我为四个终端设置变量：

在第二步中，我用变量替换终端（现在只有 S 中的产品）：

在第三步中，我将 VAB 中的 AB 替换为U -> AB：

在解决方案中，我不明白 S-productions AbB 和 bB 发生了什么（我已将其设置为 AXB 和 XB）。这是为 S-productions 提供的答案：

为什么 AbB 设置为 UX 而 bB 设置为 BX？不应该至少将 bB 设置为 XB 吗？

设n为任意终端。

考虑以下可能正确的 kleene 星在n上的表示：

（其中 ε 是空终端。）

维基百科说：

乔姆斯基范式中的每个语法都是上下文无关的，相反，每个上下文无关的语法都可以转换为乔姆斯基范式中的等效语法。

我看不出如何将上述语法转换为 CNF。

• 语法不是上下文无关的吗？
• 实际上有没有办法在 CNF 中表示它？

最终，我想将以下 CFG 转换为乔姆斯基范式：

但是，我不确定我是否正确地进行了推导——这就是我所拥有的：

用终端替换非终端

有人可以告诉我这是否正确/在正确的轨道上吗？

谢谢你。