2 개의 문맥없는 언어의 교차

Question

2 개의 문맥 자유로운 언어 (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 및 b과 같은 번호가 필요합니다. 제 2 언어에서 동일한 숫자의 b과 c이 필요하고 첫 번째 언어에서 동일한 숫자의 c과 d이 필요합니다. 따라서 동일한 숫자가 a, b, c 인 모든 단어가 필요합니다. s 및 d입니다.

그래서 기본적으로 {a^i b^i c^i d^i | i is a natural number}

주 - 결과는 문맥 자유 언어인가? 왜? ;)