context-free-language - 两种上下文无关语言的交集

Question

我在理解如何获得两种上下文无关语言(L = L1 ∩ L2)的交集时遇到了一些麻烦。我见过非常常见的例子，其中:

L1 = {a^i b^i c^j |  i,j ≥0}
L2 = {a^i b^j c^j |  i,j ≥0}
L1 ∩ L2 = {a^i b^i c^i  |  i ≥0}

但是这样的例子呢:

L1 = {a^i b^i c^j d^j |  i,j ≥0}
L2 = {a^j b^i c^i d^k |  i,j,k ≥0}
L1 ∩ L2 = ???

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

G1: S->AB
    A->aAb|λ
    B->cBd|λ

G2: S->aS|AB
    A->bAc|λ
    B->dB|λ

但在这一点上，我不知道如何将两者相交并提出一种语言。我想知道是否有人可以告诉我如何。先感谢您。

Answer 1

从第一语言开始，您需要相同数量的 a s 和 b s。从第二语言开始，您需要相同数量的 b和 c s 和从第一语言开始，您需要相同数量的 c s 和 d s - 所以所有具有相同数量 a 的单词s, b s, c s 和 d s。

所以基本上{a^i b^i c^i d^i | i is a natural number}
注意 - 结果是上下文无关语言吗？为什么？ ;)