A が有限であるか、自然数に 1 対 1 でマッピングされている場合、セット A は可算であることがわかっています。
ALPH が任意の有限アルファベットであるとします。
私の推論を要約します。
a) ALPH 上の任意の各言語はカウント可能です。（これは本当だと思います）
b) ALPH からのすべての言語のセットは可算です (これは誤りだと思います)。
c) ALPH 上の任意の言語ごとに、生成形式文法があります。(これは嘘だと思います)
d) 形式文法によって生成できる ALPH 上の任意の各言語は、再帰的です。（これは本当だと思います）
誰かが私を助けてくれますか？
一般性を失うことなく、ALPH は単なる集合 {0,1} であると仮定できます。(もちろん、その他の有限言語は、セット {0,1} を使用してエンコードできます)。言語 L によって ALPH* の任意のサブセットを意図すると仮定すると、L は {0,1}* の任意のサブセットであると想定できます。
S = {0,1}* とします。
a)集合 S は可算です。L は S の部分集合なので、L は可算です。
b) S 上のすべての言語の集合は、S の冪集合であり、実数と 1 対 1 で対応することができます。したがって、数えられません。
c)私はこれが間違っていると信じており、あなたの推測に同意します. ただし、「生成形式文法」の定義によって異なります。文法の個々の規則が決定不可能な正式な文法を許可する場合、および/または無限の生成規則を許可する場合、これはあまり明確ではなくなります。「生成形式文法」のコレクションが列挙可能である「生成形式文法」の特定の定義については、もちろん、答えは偽です。
d)一般的に、これに対する答えは誤りだと思います。文脈自由言語に対応する正式な文法に限定する場合、もちろん、あなたの答えは正しいです。ただし、http://en.wikipedia.org/wiki/Post_correspondence_problemを考慮してください 問題は決定できませんが、生成規則はかなり明確です。