两种上下文无关语言的交集

Question

我在理解如何获得两种上下文无关语言的交集（L = L1 \xe2\x88\xa9 L2）时遇到一些困难。我见过一个非常常见的例子：

\n\n

L1 = {a^i b^i c^j |  i,j \xe2\x89\xa50}\nL2 = {a^i b^j c^j |  i,j \xe2\x89\xa50}\nL1 \xe2\x88\xa9 L2 = {a^i b^i c^i  |  i \xe2\x89\xa50}\n

\n\n

但像这样的例子怎么样：

\n\n

L1 = {a^i b^i c^j d^j |  i,j \xe2\x89\xa50}\nL2 = {a^j b^i c^i d^k |  i,j,k \xe2\x89\xa50}\nL1 \xe2\x88\xa9 L2 = ???\n

\n\n

我知道我需要为两者提出上下文无关语法，我有：

\n\n

G1: S->AB\n    A->aAb|\xce\xbb\n    B->cBd|\xce\xbb\n\nG2: S->aS|AB\n    A->bAc|\xce\xbb\n    B->dB|\xce\xbb\n

\n\n

但目前，我不知道如何将两者交叉并提出一种语言。我想知道是否有人可以告诉我如何做。先感谢您。

\n

Answer 1

从第一种语言开始，您需要相同数量的as 和bs。对于第二语言，您需要相同数量的b和cs，而对于第一语言，您需要相同数量的cs 和ds - 因此所有单词都具有相同数量的as、bs、cs 和ds。

所以基本上{a^i b^i c^i d^i | i is a natural number}

注意 - 结果是上下文无关语言吗？为什么？;)