数据结构
网络
关系型数据库管理系统 (RDBMS)
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理学
化学
生物学
数学
英语
经济学
心理学
社会学
服装设计
法学消除 ε、单位和无用符号，并将文法改写成 Chomsky 范式 (CNF)
问题
消除给定文法的 ε、单位和无用符号，并将其改写成 Chomsky 范式 (CNF)。
S->0E0|1FF| ε
E->G
F->S|E
G->S| ε
解答
在给定的文法中，我们首先移除空产生式。文法中有两个空产生式，如下所示：
S ==> ε
G ==> ε
因此，移除空产生式，并用 ε 重写所有包含 G 的其他规则，同时保留旧的产生式。我们不移除 S ==> ε，因为它是一个开始符号。
移除 G ==> ε 后，我们得到：
S ==> 0E0 | 1FF | ε
E ==> G | ε
F ==> S | E
G ==> S
现在移除 E ==> ε，我们得到：
S ==> 0E0 | 1FF | 00 | ε
E ==> G
F ==> S | E | ε
G ==> S
现在移除 F ==> ε，我们得到：
S ==> 0E0 | 1FF | 00 | 1S | 1E | 1 | ε
E ==> G
F ==> S | E
G ==> S
现在，我们必须移除单位产生式，只有一个单位产生式 E ==> G 和 G ==> S，
通过移除 G ==> S，我们得到：
S ==> 0E0 | 1FF | 00 | 1S | 1E | 1 | ε
E ==> S
F ==> S | E
移除 E ==> S，我们得到：
S ==> 0S0 | 1FF | 00 | 1S | 1 | ε
F ==> S
移除 F ==> S，我们得到：
S ==> 0S0 | 1SS | 00 | 1S | 1 | ε
现在我们必须将其转换为 Chomsky 范式 (CNF)。因此，我们执行以下操作：
添加产生式 A ==> 0，B==>1，C ==> AS 和 D ==> BS，
我们得到最终文法如下：
S ==> CA | DS | BB | AS | 1 | ε
A ==> 0
B ==> 1
C ==> AS
D ==> BS
974 次浏览
