问题标签 [chomsky-normal-form]

获得CYK表后如何构建解析树？我不明白维基百科想说什么。
例子：

如何返回适用于从 A 到 BCED 的规则列表（或表格最长行的任何其他字母组合）？

嗨，我有以下 CFG

我设法删除了 epsilon，结果是：

我正在删除单元规则，这导致所有非终结符都具有相同的结果，例如：

我的问题是，我对 epsilon 的消除是否正确？有没有这样做？

我有语法S -> (S)S | empty

我把它转换成这样的乔姆斯基范式

我不确定我是否正确转换了它，但是如何使用 CNF 解析这个输入 ()()

enter code here你好，这是我的问题

为 CFL 提供上下文无关语法 L = {a^nb^mc^n | m, n ∈ N0}

我的回答是 S-> ASC| B A-> aA| a B-> bB| b C-> cC| c

不管我的回答与否？我不确定。需要一些帮助。提前致谢

所以我知道基本的 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 分钟。有没有人知道任何技巧或捷径可以让这样的事情变得更快？

谢谢。

我有以下需要转换为 CNF 的内容：

到目前为止，我所拥有的是：

是这样吗？动词和辅助会发生什么？我的书有以下内容：

1. 我认为这意味着所有带有两个非终端的规则都在正确的位置
2. Aux NP 是终端，所以我把它变成虚拟的非终端 X1 -> Aux NP

3. 不知道这一步是什么，但本书有：

   我们可以通过用它们最终导致的所有非单元生产规则的右侧重写原始规则的右侧来消除单元生产

4. 到目前为止，我所拥有的似乎是二进制的，除了动词和辅助。

假设有一个语法

• S -> PQT
• R->T
• U -> AU | bX
• X -> Y
• P -> bQ
• Y -> SX | c | X
• Q -> 阿里
• T -> U

有一个循环：

• X -> Y
• Y -> X

转换为CNF时如何消除它？我认为在语法中添加规则（如在单元消除中）X -> X 是不好的，对，因为它基本上是另一个循环？

我需要使用 Normal Order 将以下 Lambda 表达式简化为 Normal Form。这些是我的减少，但对我来说没有意义：

我得到的两个NF都没有意义。第二个是 + 函数，它需要 2 个变量，但最终只有一个。

我将不胜感激任何建议和更正。

模棱两可的上下文无关语法（CFG）是否有可能转换为乔姆斯基范式（CNF）并变得明确？

我想对此进行编码，但我被卡住了

所以假设我们有一个语法

以下是列表在每个循环之后的样子：

等等

假设我想检查字符串“(xx)”是否在语法中，所以我将进行 2n-1 次迭代，即 2x4-1=7 步。

我被困在如何编码以查看以下内容：

假设我在第 2 步。现在我想扩展 LR。我循环 LR 并将 L 扩展为相应的 RHS 值，这将是（R。这已经完成。然后我想在 LR 中扩展 R 现在我必须使用 L 而不是（这样我才能实现 L）。循环时如何当我的索引移动到 R 时我得到 L？

假设我正在扩展 S->LR RHS rhs 是一个列表列表

我的问题

在展开第 n 项时，如何将剩余的右手项添加到当前展开中以及如何添加当前展开的左手项。

示例：我正在扩展 LR。如果 L 然后 (R 所以我必须添加 R

谢谢