上下文无关语法?
我遇到这个问题,我需要将以下 CFG 转换为 CNF 中的 CFG。
S-> ABa
A-> aab
B-> Ac
我知道步骤如下。
- 删除 epsilon 转换 - 通过以下方式完成
- 删除单位产生式
- 转换为 CNF:
- 为每个术语引入一个新的非终结符
- 用新的非终结符替换产生式规则中的终结符
- 引入新的非终结符以减少每个产生式右侧的长度
我对如何使用新的非终结符来做到这一点有点困惑问题如上。我主要对步骤 2 和单元制作感到困惑。
I have this problem where I need to convert the following CFG to CFG in CNF.
S-> ABa
A-> aab
B-> Ac
I know the steps are as follows.
- Remove epsilon transitions - Done
- remove unit productions
- convert to CNF by:
- introduce a new non terminal for each term
- replace terminals in the productions rules with the new nonterminal
- introduce new nonterminals to reduce the length of the right side of each production
I'm a bit confused on how I would do that with the problem above. Mostly I am confused on step 2 and unit productions.
如果你对这篇内容有疑问,欢迎到本站社区发帖提问 参与讨论,获取更多帮助,或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱,如果其他用户或者作者回复了您的评论,将不能在第一时间通知您!
发布评论
评论(2)
步骤 1 和 2 已经完成。所以我们只需要担心第 3 步。
开始语法:
为每个术语引入一个新的非终结符。
<前><代码>S ->阿巴
A->阿布
B->乙酰胆碱
C->一个
D->乙
E-> c
用新的非终结符替换产生式规则中的终结符。
<前><代码>S -> ABC
A-> CCD
B-> AE
C->一个
D->乙
E-> c
引入新的非终结符以减少每个产生式右侧的长度。
<前><代码>S -> AF
A-> CG
B-> AE
C->一个
D->乙
E-> c
F->公元前
G->光盘
Steps 1 and 2 are already complete. So we only need to worry about step 3.
Starting Grammar:
Introduce a new non terminal for each term.
Replace terminals in the productions rules with the new nonterminal.
Introduce new nonterminals to reduce the length of the right side of each production.