问题标签 [chomsky-normal-form]

谁能告诉我是否有任何软件可以将乔姆斯基范式转换为巴科斯-瑙尔范式，反之亦然？

我有这个问题，我需要在 CNF 中将以下 CFG 转换为 CFG。

我知道步骤如下。

1. 删除 epsilon 转换 - 完成
2. 删除单元制作
3. 通过以下方式转换为 CNF：
   1. 为每个术语引入一个新的非终结符
   2. 用新的非终结符替换产生式规则中的终结符
   3. 引入新的非终结符以减少每个产生式右侧的长度

我对如何解决上述问题感到有些困惑。大多数情况下，我对第 2 步和单元制作感到困惑。

我正在尝试做一个练习，将语法翻译成乔姆斯基范式。我知道在正常情况下如何做到这一点，但这次我使用的语法是正确的递归。（从技术上讲，语法是前一个问题的答案，所以我可能只是有错误的伽玛。）

我想我可以通过使用固定的规则序列代替 ε 规则来做到这一点，但我想确保我没有走错方向。用一个例子更容易解释：

对于产生 n 'a 的语法，其中 n 大于 0 和三的倍数：（别担心，这与我实际练习的语法完全不同）

正确的翻译是：

为所有单词的语言 L 找到上下文无关文法 (CFG)，使得单词中的每个终结符在可能较大的字母表 Σ 上出现偶数次

我的长期方法是（唯一的非终结符是 S）：

这个对吗？产生式生成正确的单词，它们会生成所有单词吗？

编辑：大字母表上的 CFG 能否描述一种语言，每个终端出现偶数次？

EDIT_2：如果存在解决方案，乔姆斯基范式是否可能是 |Σ| 中的多项式？?

我想将语法更改为乔姆斯基范式（CNF）。

这是示例

我试图解决这个问题

我不确定答案。谁能告诉我这是对还是错？

why do we convert the grammar to chomsky normal form ? Is there a advantage ?

我确实需要你的帮助。我有这些作品：

我应该应用乔姆斯基范式（CNF）。

为了应用上述规则，我应该：

1. 消除ε产生
2. 消除酉产生
3. 删除无用的符号

我马上就卡住了。原因是 A 是可以为空的符号（ε 是其主体的一部分）

当然，我不能删除 A 符号。

谁能帮我得到最终的解决方案？

我有这些作品：

我应该应用乔姆斯基范式

我的推理：

1）消除eps规则给定：

我得到：

2）消除单位规则

没有了

3) 删除无用符号

我得到：

因此，应用 CNF（乔姆斯基范式）后的给定语法变为：

我对吗？

将下面的语法转换为乔姆斯基范式。给出所有中间步骤。

好的，所以我做的第一件事就是添加一个新的开始变量S0

所以现在我有

然后我删除了所有的 lambda 规则：

然后我检查S->S并A->B键入不存在的规则。这就是我想出的答案，我需要做进一步的事情还是我做错了什么？

我正在使用 CFG，每次我为特定语言编写规则时，我的 CFG 最终都会令人作呕。它以一行结束：

我知道将东西放入 chomsky 范式会使其格式正确，并且会更漂亮，但我想知道是否有任何想法可以让这些看起来不那么混乱。

即，朗：

我的 CFG（总）：

谁能帮我改掉我的坏习惯？