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|λ

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

score 4 · Accepted Answer

从第一种语言开始，您需要相同数量的as 和bs。在第二种语言中，您需要相同数量的band cs，而在第一种语言中，您需要相同数量的cs 和ds - 所以所有具有相同数量as、bs、cs 和ds 的单词。

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

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

1 回答 1