我们知道如果 A 是有限的或在与自然数的一对一映射中，集合 A 是可数的。
假设 ALPH 是任意有限字母表。
我总结一下我的推论：
a) ALPH 上的每种任意语言都是可数的。（我认为这是真的）
b) 来自 ALPH 的所有语言的集合都是可数的。（我认为这是错误的）
c) 对于 ALPH 上的每种任意语言，我们都有一个生成形式语法。（我认为这是错误的）
d) 可以由形式文法生成的 ALPH 上的每种任意语言都是递归的。（我认为这是真的）
任何人都可以帮助我，也许纠正我？
user4110176
问问题
79 次
1 回答
0
不失一般性，我们可以假设 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 问题是无法确定的，但生成规则非常明确。
于 2014-10-05T17:56:35.957 回答