1. ホーム
  2. 質問と答え
  3. 2つのコンテキストフリー言語の設定の相違は、コンテキストフリーですか？

2つのコンテキストフリー言語の設定の相違は、コンテキストフリーですか？

2017-05-19 16 views
1

私はインターネットで検索しましたが、文脈自由言語 は、組合、連結、逆転、およびKleene Starのために閉じられていると言います。彼らはまたセットの違いのために閉鎖されていますか？2つのコンテキストフリー言語の設定の相違は、コンテキストフリーですか？

出典

2017-05-19 JohnnyBoi

+1

私はプログラミングに関するCS理論ではないので、この質問を議論の対象にしないように投票しています。 –

答えて

2

コンテキストのない言語は、設定の違いで閉じられません。これを見るための一つの方法は、言語Σ

  • 、

    1. 文脈自由言語は補完の下で閉じていないことに注意することがある*すべての言語Lの補完のための文脈自由で、かつ
    2. LはΣ *で与えられる - CFLのは、差集合の下で閉じた場合、彼らはありませんことを除いてL.

    したがって、それらは...補完の下で閉じているはずです。 :-)

    • 出典

    2017-05-20 00:01:33 templatetypedef

    関連する問題

     関連する問題