文脈自由な言語と通常の言語との共通部分は常に文脈自由ですが、文脈自由言語は集合交差の下で閉じられません。誰もが、通常のすべての言語が文脈自由であれば(なぜなら、その逆は常に真ではない)、両方の定理が真である理由を説明できますか?文脈自由言語のクロージング特性および規則的言語との交差
2
A
答えて
6
文脈自由言語が交差点で閉じられていないことを証明するために、反例を提供します。
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台のマシンだけがスタックを必要とします。
関連する問題
- 1. プッシュダウンオートマトンと無限要素を含む文脈自由で規則的な言語
- 2. 文脈自由言語の連合
- 3. 設定、レジストリ、および言語の名前の規則
- 4. 言語から文脈自由文法への移動
- 5. 束縛された文脈、サブドメインおよびユビキタス言語
- 6. C言語を文脈自由にするには?
- 7. T-SQL言語仕様とレキシング規則
- 8. 次の言語のための文脈自由文法を書く
- 9. c言語のデータ型算術規則
- 10. 次の言語を生成する文脈自由文法を与える
- 11. 自然言語コマンド言語
- 12. 異なるプログラミング言語と呼び出し規則
- 13. 文脈自由言語で1または2の右側変数
- 14. 私は基本的に前記大学の作業であった文脈自由言語と無限定期的なサブ言語
- 15. 不規則な規則で言語に翻訳する
- 16. 形式0^n(nは素数)の言語が規則的でも文脈自由でもないことを証明する
- 17. 通常の言語と文脈自由な言語が再帰的であることを証明してください。
- 18. 文脈自由文法の左回帰規則
- 19. RealURLはprevar言語およびパラメータ
- 20. SEOおよびマルチ言語サポート
- 21. 正規言語
- 22. PHPは完全に文脈自由言語ですか、文脈依存部分を持っていますか?
- 23. 宣言的言語のXSLT
- 24. 自然言語とプログラミング言語の文法上の違いは何ですか?
- 25. VimとPython:言語メソッドの文脈に依存しないオートコンプリート
- 26. Pythonの:言語的正規化
- 27. 言語機能直交?
- 28. AVRアセンブリ言語 - 交通ライト
- 29. JavaとC言語の速度の差
- 30. HTL言語、文字列連結および3進演算子
お返事ありがとうございます!私は適切なサブセットについて考えていなかったが、今はすべて意味がある。 – methane
それは良い質問です、私はあなたが私の答えが好きとうれしいです。つまり、これがあなたの質問に対する良い答えだと思うなら、それを受け入れる(緑になるようにチェックマークをクリックする)ことで、コミュニティの他の人が良い答えを識別しやすくなります。 – Patrick87
私はRの文法に型があると信じます。それは "abacc"も受け入れます。 S:= aSc | B B:= bB |ラムダ –