使用CFG构建一对语言

问题

考虑以下上下文无关文法 (CFG)，并找出可以分别由 G1 和 G2 生成的语言对。

解决方案

考虑以下CFG -

G1 : S->aS|B , B->bl bB

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}