为给定的上下文无关文法生成 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