3

文脈自由言語と通常の言語の交差は常に文脈自由ですが、文脈自由言語は集合交差の下で閉じられません。すべての通常の言語が文脈自由である場合、両方の定理が真である理由を誰か説明できますか (反対は常に真であるとは限りません)。

4

1 に答える 1

7

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

L = {a^ib^jc^k | i = j} および R = {a^ib^jc^k | 私は= k}。これら 2 つの集合の交点は S = {a^ib^jc^k | i = j = k}、つまり a^nb^nc^n の形式の文字列。文脈自由言語のポンピング補題を使用して、この言語が文脈自由でないことを示すことができます。他の 2 つの文脈自由文法は簡単です。

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

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

より具体的に質問に答えるために、両方の定理が真である理由は、通常の言語が文脈自由言語の適切なサブセットであるためです。文脈自由言語が設定された交差の下で閉じられるようにするには、任意の文脈自由言語の交差も文脈自由でなければなりません (そうではありません。上記を参照してください)。しかし、正規言語と文脈自由言語の共通部分もまた文脈自由であるということは同時に真実です (デカルト積機械が FA とPDA; 結局、1 つのマシンだけがスタックを必要とします - 場合によっては 2 つのスタックが必要であり、2 つのスタック PDA はチューリング マシンと同等であるため、2 つの PDA でデカルト積マシンを試す場合はそうではありません)。

于 2011-08-11T15:51:35.223 に答える