在 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
现在，每个产生式生成一个终端或两个非终端。