在 CNF 中设计一个明确的 CFG 来生成 E?

问题

定义语言 E={aibj|i 不等于 j 且 i 不等于 2j} 并设计生成 E 的乔姆斯基范式 (CNF) 中的无歧义上下文无关文法 (CFG)。

解决方案

给定语言的明确 CFG 如下 -

S->AC|CB

A->aA|a

B->Bb|b

C->aCb|aaCb|epsilon

现在，将此 CFG 转换为 CNF。您可以按照以下提到的步骤成功转换。

第1步

首先添加一个新的起始符号S0

   S0->S

   S->AC|CB

   A->aA|a

   B->Bb|b

   C->aCb|aaCb|epsilon

第2步

接下来消除除开始符号之外的产生式中的 epsilon 符号。

   C->epsilon 是一个空产生式

消除空生产后，新的生产如下 -

   S0->S

   S->AC|CB

   A->aA|a

   B->Bb|b

   C->aCb|aaCb|ab|aab

第 3 步

现在删除单位生产，如果它存在

S0->S 是单位产量

替换 S，用 S 生产

   S0->AC|CB

   S->AC|CB

   A->aA|a

   B->Bb|b

   C->aCb|aaCb|ab|aab

第四步

没有无用的产品可以删除。

第 5 步

现在检查不在CNF中的产生式，如果没有，让我们转换成CNF

如果产生式规则满足以下条件之一，则上下文无关文法在 CNF 中 -

• 如果有开始符号生成ε。示例 - A->

• 如果一个非终结符产生两个非终结符。示例 - S->AB

• 如果一个非终端产生一个终端。示例 - S->a

现在，我们的语法不遵循下面给出的规则 -

   A->aA

   乙->乙

   C->aCb|aaCb

将此产生式转换为 CNF，如下所示 -

   A->XA

   B->BY

   C->XCY|XXCY

   X->a

   Y->b

仍然 C->XCY|XXCY 违反规则，因为 RHS 有两个以上的符号 所以，让我们分解产生式

   C->XCY

   C->RY

   R->XC

和

   C->XXY

   C->LM

   L->XX

   M->CY

生成 E 的 CNF 如下 -

   S0->AC|CB

   S->AC|CB

   A->XA|a

   B->BY|b

   C->RY

   C->LM

   X->a

   Y->b

   R->XC

   L->XX

   M->CY

现在，每个产生式生成一个终端或两个非终端。