为给定的上下文无关文法生成乔姆斯基范式 (CNF)

问题

为以下上下文无关文法 (CFG) 生成乔姆斯基范式 (CNF)。

S->aAa|bBb|e

A->C|a

B->C|b

C->CDE|e

D->A|B|ab

解答

按照以下步骤生成给定 CFG 的 CNF

步骤 1 - 消除空产生式 (∧-productions)

我们可以删除或消除空产生式，并处理重复。

S --> aAa | bBb | ∧

A --> a | ∧

B --> b | ∧

D --> A | B | ab

步骤 2 - 消除上述文法中的单元产生式

消除右部只有一个符号的产生式

S --> aDa | bDb

D --> a | b | ab

步骤 3 - 消除无用符号

E 是给定文法中的无用符号，因为它在右部没有导出。

S --> aDa | bDb

D --> a | b | ab

步骤 4 - 乔姆斯基范式 (CNF)

获取其体是终结符和变量的混合，或由多个终结符组成的产生式

将产生式分解成如下所示的简短形式

S --> XYX | ZYZ

S --> XP | ZQ

P --> YX

Q --> YZ

X --> a

Y --> a | b | ab

Z --> b

Bhanu Priya

更新于：2021年6月12日

946 次浏览

启动您的 职业生涯

完成课程获得认证

开始学习