问题标签 [chomsky-normal-form]

鉴于：

我不确定如何继续。

I started solving it but it seems I just kept on adding new rules to keep up, can someone please explain how to do this one.

CFG 的著名形式之一是 CNF，如您所知，它有两个非终端作为其 RHS 或一个终端作为其 RHS 和空 RHS，如果存在，则仅出现在本Wiki中描述的根的 RHS 中，但我不是确定 CNF 允许我们进行左递归吗？

我一直在尝试根据维基百科给出的伪代码来实现 CYK 算法，但是我似乎无法做到正确，也不知道代码有什么问题。我最好的猜测是我的索引是错误的，因为伪代码不使用数组索引。

这是我正在测试的语法：
/ --> U1V1 | U2V2 | V1V1 | V2V2 | 一个 | b
S --> U1V1 | U2V2 | V1V1 | V2V2 | 一个 | b
V1 --> a
V2 --> b
U1 --> V1S
U2 -- > V2S
这个语法接受回文，所以应该接受“baab”，但是它不被接受为语法的一部分

下面是代码：

辅助函数只返回变量的所有给定产生式及其在变量向量中的索引 {/,S,V1,V2,U1,U2}

此文法（在 CNF 中）来自转换后的文法 S>aSa|bSb|aa|bb|a|b（不在 CNF 中）

任何帮助将不胜感激

我正在尝试用尽可能少的作品以乔姆斯基范式构造一个 CFG，它接受包含唯一字符串 a^21 的语言。

我知道我可以转换

S -> AAAAAAAAAAAAAAAAAAAAA A -> a

但是有没有其他方法可以缩短该语言然后将其转换为乔姆斯基范式？

我已经阅读了许多 CYK/CKY 算法要求语法采用乔姆斯基范式 (CNF) 的地方，例如

CYK 的标准版本仅适用于以乔姆斯基范式 (CNF) 给出的上下文无关文法 ~维基百科

但是，我还看到了许多 CKY 算法的示例，其中语法不在 CNF 中。Christopher Manning 使用的一个常见示例是“鱼人鱼缸”（参考：PPT 幻灯片 #19），其中包含一元规则：

我还看到了演示 CKY 的其他示例，这些示例在生产的 RHS 中使用了三个非终端（例如VP -> Verb NP NP reference）。为什么会出现差异？

当我们要将语法转换为乔姆斯基范式时，为什么要添加新的起始状态 S0 -> S？如果我们不这样做，会出现什么问题？

起初我认为这是因为 epsilon 规则。但是我们不会从 start 变量中删除 epsilon 规则。那么，添加 S0 -> S 有什么好处呢？

谢谢

我正在尝试从这种语言构造一个 CFG：

如果我理解正确，我得到了

但即使这是正确的，我也不确定如何从中制作乔姆斯基范式的 CFG。我知道的每一条规则都适用于此。所以我认为我的第一个 CFG 出错了？

如果 PCFG 是这样的，

什么是 CNF 形式？会是以下吗？

还是别的什么？

我想知道两种语言（一种常规语言和另一种非常规语言）之间的连接是否总是不规则的，或者输出可能是常规语言。谢谢。