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|λ
しかし、この時点では、この 2 つを交差させて言語を作成する方法がわかりません。誰かが私に方法を教えてくれるかどうか疑問に思っていました。前もって感謝します。