问题标签 [chomsky-normal-form]

1. 使用正则语言的抽引引理，证明

   语言 L = { a ⁱ , b ^j c ^k | i, j, k 是非负整数，并且 i=j 或 i=k }

不规则

2. 为上述语言设计 CFG

这就是我想出的

现在我必须将上面的 CFG 转换为我遇到问题的 chomsky 范式......有什么帮助吗？

我对何时使用 CNF 转换的第一步感到困惑。

第一步：ensure s does not appear on rhs, add new S0 if necessary and copy all rules of S

我不清楚上述声明的含义。我不知道何时创建 S0。有些 CFG 不以 S0 开头，有些则以 S0 开头。

兄弟们在这里有点帮助。

我目前正在学习CNF，我有点困惑。

鉴于此语法：

S -> ab | aSb

将导致 CNF：

S -> AB | XB

X -> AY

Y -> AB | XB

A -> a

B -> b

这个怎么样：

S -> c | aSa | bSb

有人可以在这方面给我一点帮助吗？谢谢。

Consider the context-free grammar G = ( { S, B, E }, { 0, 1, i, e, s }, R, S ), where R is:

Alrighty, so I removed the lambda and got:

And now I'm trying to remove the unit/chain rules and the rest, and this is what I have so far:

But I know S0 --> X and S --> BSE are not valid. How can I fix this? Thank you for any help! :)

我正在将 CFG 转换为乔姆斯基范式，但我遇到了一些困难。

我有这个 CFG

A-> BAB|B|epsilon B -> 00|epsilon

好的，我添加了一个新的开始状态

S -> A A-> BAB|B|epsilon B -> 00|epsilon

然后我必须删除 epsilon 转换，所以我从 B 开始

S -> A A-> BAB|B|AB|BA|A|epsilon B -> 00

然后如何从 A 中删除 epsilon？开头可以有一个epsilon吗？以及如何转换 A-> A？

我正在尝试通过向 nltk.cfg 提供一堆语法产品来使用 CNF 语法，例如：

但它有问题（给出错误：预期的箭头）与在产品左侧有管道的产品。例子：

nltk 是否有任何语法方法对左侧的管道没有问题？

如果没有，我怎样才能将所有这些作品更改为像第一组这样的可用作品？例子：

我正在尝试从其解析树中提取乔姆斯基范式（CNF） - 句子的语法产生：

我将整棵树放入一个名为 S 的字符串中，然后：

输出是

但有些作品（7 号和 8 号）似乎不是 CNF！问题是什么？

鉴于此 CFG

我尝试转换为 CNF

首先删除 Null 产品，即 S->^ 和 C->^

所以删除后

现在删除单位产品，即 S->B、A->C、S->A 和 C->S

所以添加这些产品

其中 K->q,U->p

CNF 中所需的 CNG 是

R->UC

这是正确的吗？

我认为当 Y 只有 Z 作为它的终端时，ε 移动到 Y 给出：

然后？

我在语法中有这个规则：

我想将此 PCFG（概率上下文无关语法）转换为 CNF（乔姆斯基范式）

为此，我知道我们可以将规则拆分为两个非终结符

为每个规则设置哪个概率？

谢谢