我们知道，如果A是有限的，或者在与自然数的一对一映射中，集合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）总的来说，我认为这个问题的答案是false。如果你把自己局限于与上下文无关的语言相对应的形式语法，那么你的答案当然是正确的。但是，请考虑http://en.wikipedia.org/wiki/Post_correspondence_problem这个问题是不可决定的，但生成规则非常明确。