为给定的上下文无关文法生成 CNF
问题
为以下上下文无关文法 (CFG) 生成乔姆斯基范式 (CNF)。
S->aAa|bbBb|e
A->C|a
B->C|b
C->CDE|e
D->A|B|ab
解决方案
按照下面提到的步骤为给定的 CFG 生成 CNF
步骤 1 - 消除 ∧ -生产
我们可以删除、擦除或 ∧ -生产双倍重复。
S --> aAa | bbb | ∧
一个 --> 一个 | ∧
乙 --> 乙 | ∧
D --> A | 乙 | AB
Step 2 - 消除上述语法中的单元产生式
消除 RHS 单一符号产生式
S --> aDa | 数据库
D --> 一个 | 乙 | AB
步骤 3 - 消除无用的符号
E 是给定语法中的无用符号，因为它不是 RHS 中的派生词。
S --> aDa | 数据库
D --> 一个 | 乙 | AB
步骤 4 - 乔姆斯基范式 (CNF)
获取其主体是终端和变量的混合体，或由多个终端组成的产生式
分解短形式的制作，如下所示
S--> XYX | ZYZ
S--> XP | 中青
P --> YX
问--> YZ
X --> 一个
是 --> 一个 | 乙 | AB
Z --> b
以上是 为给定的上下文无关文法生成 CNF 的全部内容， 来源链接： utcz.com/z/341389.html
