context-free-grammar - 如何在 CNF 中找到这个语法

Question

我需要帮助解决 CNF 的语法：S->SS|(S)|e

我查看了将其发送到 CNF 的步骤，但我的问题是如何使用 () 为语法解决它，因为语法变得非法

任何人。

Answer 1

这应该是 CNF 中的等效语法：

S -> SS|CB|e
A -> (
B -> )
C -> AS

编辑：对于 CNF 中的语法S -> SS|(S)|ε 第一步是删除 ε（简化为删除冗余规则）

S -> SS|S|(S)|()

下一步是删除单元制作。在这种情况下，您只有一个生产规则，因此我们可以删除 UP，因为它只会添加冗余规则。

S -> SS|(S)|()

最后一步是添加生产规则以遵守 CNF（单个终端或恰好 2 个变量）：

S -> SS|CB|AB
A -> (
B -> )
C -> AS

请记住，CNF 从语法生成的语言中删除了“ε”。否则语法等同于原文。