数据结构
网络
RDBMS
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理学
化学
生物
数学
英语
经济学
心理学
社会学
时尚研究
法律研究使用 CFG 构建一对语言
问题
考虑以下上下文无关文法 (CFG)，找出 G1 和 G2 分别可以生成的语言对。
解决方案
考虑以下 CFG −
G1 : S->aS|B , B->b l bB
G2: S->aA | bB , A->aA| B | ε , B->bB | ε
现在，我们可以按以下步骤生成语言。首先考虑 G1，如下所示
Consider G1: S->aS|B B->b|bB Using S->B ->b b can be generated Using S->B ->bB ->bb bb can be generated Using S->aS ->aB ->ab ab can be generated Using S->aS ->aB ->abB ->abb abb can be generated
可以看到，a 的个数可以为 0 也可能大于 0，但是 b 的个数总大于 0。
因此，结果将如下所示 −
L(G1)= {ambn | m>=0 & n>0 }现在，考虑 G2，如下所示 −
Consider G2: S->aA|bB A->aA|B| ε B->bB| ε Using S->aA ->a a can be generated Using S->bB ->b b can be generated Using S->aA ->aaA ->aa aa can be generated Using S->bB ->bbB ->bb bb can be generated Using S->aA ->aB ->abB ->abb abb can be generated
可以看到，a 和 b 中必须有一个大于 0。
因此，结果将如下所示 −
L(G2)= {aman |m>0 or n>0}
更新于: 2021 年 6 月 12 日
200 次浏览
广告