通常言語の無限連合

Question

無限の正規言語連合は文脈自由であることができます。

このステートメントは、trueまたはfalseですか？

回答キーによれば、これは本当です！私が知っていることは、無限の組合や交差点が組合/交差点で閉鎖されていないということです。

誰でもこの背後にある手順やロジックについて説明できますか？特定の言語の無限組合/交差点を知るには？

Answer 1

ステートメントはtrueです。そのような組合が文脈自由であるかどうかを尋ねる。常にそうではない。 verxの単純な例は、無限に同じ言語の連合をとっています。結果は元の言語に過ぎず、それが正規であれば結果も同じです。あるいは、すべての{a^i}の和集合は普通の言語a^*です。

一方、無限組合は、計算できないことがあります。列挙できない言語Lと、この言語の正確に一つの単語を含む無限に多い（普通の）シングルトン集合を取る。彼らの組合はLであり、従って列挙できない。