使用CFG构建一对语言
问题
考虑以下上下文无关文法(CFG)，并找出可以分别由G1和G2生成的语言对。
解决方案
考虑以下CFG-
G1:S->aS|B,B->blbB
G2：S->aA|bB,A->aA|乙|ε,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的数量可以是零或更多，但b的数量总是大于零。
因此，结果如下-
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必须大于零。
因此，结果如下-
L(G2)= {aman |m>0 or n>0}