数据结构
网络
关系数据库管理系统(RDBMS)
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C语言编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理学
化学
生物学
数学
英语
经济学
心理学
社会学
服装设计
法学设计一个在CNF中生成E的无歧义CFG。
问题
定义语言E={aibj|i ≠ j且i ≠ 2j}，并设计一个在乔姆斯基范式(CNF)中生成E的无歧义上下文无关文法(CFG)。
解答
给定语言的无歧义CFG如下：
S->AC|CB
A->aA|a
B->Bb|b
C->aCb|aaCb|ε
现在，将此CFG转换为CNF。您可以按照以下步骤成功转换。
步骤1
首先添加一个新的起始符号S0
S0->S
S->AC|CB
A->aA|a
B->Bb|b
C->aCb|aaCb|ε
步骤2
接下来，消除除起始符号之外产生式中的ε符号。
C->ε是一个空产生式
消除空产生式后，新的产生式如下：
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
步骤4
没有无用的产生式需要移除。
步骤5
现在检查不符合CNF的产生式，如果不符合，则将其转换为CNF。
如果产生式规则满足以下条件之一，则上下文无关文法处于CNF中：
- 如果存在起始符号生成ε。例如：A->ε
- 如果一个非终结符生成两个非终结符。例如：S->AB
- 如果一个非终结符生成一个终结符。例如：S->a
现在，我们的文法不遵循以下规则：
A->aA
B->Bb
C->aCb|aaCb
将此产生式转换为CNF，如下所示：
A->XA
B->BY
C->XCY|XXCY
X->a
Y->b
仍然C->XCY|XXCY违反规则，因为右边有超过两个符号。因此，让我们分解产生式
C->XCY
C->RY
R->XC
以及
C->XXCY
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
现在，每个产生式要么生成一个终结符，要么生成两个非终结符。
203 次浏览
