语言是用一些有限的字母表写成的一组可能无限的有限词。由于字母表是有限的,每个单词的长度也是有限的,因此任何语言的单词都是可枚举的,从存在枚举的意义上说。换句话说,任何语言的大小至多是可数无限的。
但是,由于字母表的 Kleene 闭包的任何子集都是一种语言,因此语言的数量不是无限的。因此,没有语言的枚举。
乔姆斯基层次结构基于一种形式,可以表示为具有有限字母的有限句子(与所描述的语言相同的字母,加上几个额外的符号)。[注 1] 所以可能的 Type 0 文法的数量是可数无限的,文法集和语言集之间不存在对应关系。
然而。不存在生成语法的语言(即集合)的存在并不一定意味着存在比生成语法“更具表现力”的其他方式来描述这些语言。任何可以使用有限字母表写成有限字符串的描述只能描述可数的无穷集合。是否相同的可数无穷大取决于形式,并且通常不会有可以证明同态的算法。但是一些等价是已知的(例如与图灵机的等价,这是一个特别有趣的等价)。
所以,我们有一个有趣的小难题,它(当然)与哥德尔的不完备性定理有关。也就是说,无论我们使用什么系统来描述一种语言,语言都比描述语言的方式多。所以问题是“我们如何描述一种没有可用描述的语言?” 没有一个好的答案(如果我们通过调用某个集合“Sue”来回答它,那么仍然会有无数个不存在名称的可能集合)。
虽然所有这些无限的探索都很有趣,但它有一些问题:
它与编程几乎没有关系(如果有的话),因此它是否是 StackOverflow 的主题值得怀疑。
Kurt Gödel 和 Georg Cantor 这两位数学家负责这个答案中的大部分概念,他们都患有严重的抑郁症。只是说。
笔记
- 尽管乍一看,Type 0 语法的字母表可能比所描述语言的字母表任意大,但实际上并非如此。语法的字母表由目标字母表加上一组有限的非终结符加上一个→符号组成;可以使用任何方便的基数(例如二进制)来编写非终结符。所以只需要三个额外的符号(你可以通过任意指定一个非终端数字作为箭头将其减少到两个)。(看起来您似乎需要第三个符号来分隔非终结符的名称,但您可以使用斐波那契编码来生成始终以 1 开头且从不包含两个 1 的代码,这样您就可以在开始明确地标记符号的开始。)