intersection - 言語が文脈自由かどうかを判断する

Question

言語 L があり、それが文脈自由かどうかを判断したいとしましょう。通常の言語と交差する文脈自由言語は、文脈自由です。L が文脈自由であることを証明するのに十分ですか?

意味、

L は P = T と交差します。ここで、P は通常の言語であり、T は文脈自由です。これは、L が文脈自由であることを意味しますか?

Answer 1

いいえ、あなたの発言は真実ではありません。次の反例を考えてみましょう。

L = {0n1n2n | n > 0}, P = T = Ø. 明らかにL ∩ P = L ∩ Ø = Ø = T、 があり、Øは規則的で文脈自由です。

Lは文脈自由ではないことはよく知られていることに注意してください(補題のポンピングによるスケッチ証明については、p.12 の例を参照してください)。