数据结构
网络
关系数据库管理系统
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理学
化学
生物学
数学
英语
经济学
心理学
社会学
时尚研究
法律研究将给定的上下文无关文法转换为 Chomsky 范式 (CNF)
问题
将给定的语法转换为 Chomsky 范式 (CNF)
S->AAA|B
A->aA|B
B-> ε
解决方案
按照以下步骤将 CFG 转换为 CNF -
步骤 1 - 消除 ε 生成式
要消除 ε 生成式，必须在所有其他生成式的 RHS 中替换产生 ε 的变量，以移除 ε 生成式。
在所有其他生成式中用 ε 替换 B 得到以下生成式集 -
S-> AAA | ε | B
A->aA | ε | B
在所有其他生成式中用 \epsilon 替换 A 得到以下结果 -
S ->AAA | AA | A | B | ε [分别用 ε 替换 1、2 和 3 个 A]
A->aA | a | B
由于语法生成字符串 ε，因此为了使语法保持等价，无法消除剩余的 ε 生成式。移除最终的 ε 生成式得到一个语法 G'，该语法与原始语法 G 具有以下关系 -
L(G') = L(G) -{ ε }
G' 中的生成式如下 -
S -> AAA | AA | A | B
A -> aA | a | B
步骤 2 - 消除单元生成式
消除单元生成式的过程如下 -
选择一个生成式 A-> B，使得存在非单元生成式 B-> a
对于每个非单元生成式 B-> a，重复以下步骤 -
向语法中添加生成式 A->a。
从语法中消除 A->B。
从语法中消除单元生成式 S-> A，得到以下语法 -
S ->AAA | AA | aA | a | B
A -> aA | a | B
B 没有生成式，因此无法消除类型 V -> B 的单元生成式。
步骤 3 - 无用符号
B 是一个无用符号，因为它没有生成式。因此可以移除它。
A-> a 导致生成一个终结符字符串，并且它可以从 S 访问，因此 A 不是无用的
类似地，S 也不无用，因为可以从中生成终结符。
因此，移除无用符号后的结果 CFG 为 -
S->AAA | AA | aA | a
A->aA | a
Chomsky 范式 (CNF)
要将语法转换为 Chomsky 范式，需要将右侧有多于两个元素的所有生成式拆分为两个或多个生成式，方法是添加更多变量。
右侧至少有两个符号的生成式中的终结符需要替换为变量符号。
添加以下生成式以生成终结符 a -
Z->a
结果语法如下 -
S-> AAA | AA | ZA | a
A-> ZA | a
Z -> a
生成式 S ->AAA 通过添加一个额外的变量 T 进行修改。
这给出了以下语法 -
S -> TA | AA | ZA | a
T ->AA
A -> ZA | a
Z -> a
在上述语法中，所有生成式都为 A -> BC 或 A ->b 的形式。因此，它处于 Chomsky 范式 (CNF)。
18K+ 次查看
