文脈自由言語のクロージング特性および規則的言語との交差

Question

文脈自由な言語と通常の言語との共通部分は常に文脈自由ですが、文脈自由言語は集合交差の下で閉じられません。誰もが、通常のすべての言語が文脈自由であれば（なぜなら、その逆は常に真ではない）、両方の定理が真である理由を説明できますか？

Answer 1

文脈自由言語が交差点で閉じられていないことを証明するために、反例を提供します。

L = {a^i b^j c^k | i = j}であり、R = {a^i b^j c^k | i = k}である。これらの2つの集合の交点はS = {a^i b^j c^k | i = j = k}、すなわち、a^n b^n c^nの形式の文字列である。これは、文脈自由言語のポンピング補題を使用して、この文脈が文脈自由ではないことを示すことができる。他の二つのための文脈自由文法は簡単です：

L is given by 
    S := AC 
    A := aAb | lambda 
    C := cC | lambda 

    R is given by 
    S := aSc | B | lambda 
    B := bB | lambda 

より具体的にあなたの質問に対処するために、両方の定理が真であることが可能な理由は、正規言語は文脈自由言語の適切なサブセットであるということです。文脈自由言語が集合交差点の下で閉じられるためには、任意の文脈自由言語の共通部分も文脈自由でなければならない（それは上で見ていない）。しかし、それと同時に、正規言語と文脈自由言語の共通部分も文脈自由であるという事実が起こることは事実である（FAとaを使ってデカルト積の機械を作ることはできないPDAという2つのスタックを必要とし、2つのスタック型PDAはチューリングマシンと同等であるため、1台のマシンだけがスタックを必要とします。