0

我问这个问题是因为我偶然发现了乔姆斯基语言类型的公认答案

这句话指的是 Type-0 语法：

这意味着如果你有一种比这种类型更具表现力的语言（例如英语），你就不能编写一个算法来列出该语言的每一个（并且只有这些）单词

据我所知：

  • 英语是什么没有数学描述，因此争论它在形式语言层次结构中的位置是没有意义的。
  • 如果有，那么英语肯定会被一些 Type-0 语法识别，因为它是由有限数量的推理定义的——它可以是公理、语法等等。（如果不是——如果不是通过有限的步骤，别人怎么能定义它？）

因此：

  • 我们不能开始谈论语法需要多么“富有表现力”才能精确地生成一个未知的数学对象

因此我的问题：

  • 如何定义一种不符合乔姆斯基层次结构的语言？
  • 如果（？）数学家需要有限数量的步骤来定义具有不使它们递归可枚举的基数的集合 - 那么必须存在比 Type-0 更具表现力的文法，因为它们（数学家）遵循有限数量的规则（生产规则，如果你愿意的话）生产一个非 RE 集。他们在哪？
4

1 回答 1

3

语言是用一些有限的字母表写成的一组可能无限的有限词。由于字母表是有限的，每个单词的长度也是有限的，因此任何语言的单词都是可枚举的，从存在枚举的意义上说。换句话说，任何语言的大小至多是可数无限的。

但是，由于字母表的 Kleene 闭包的任何子集都是一种语言，因此语言的数量不是无限的。因此，没有语言的枚举。

乔姆斯基层次结构基于一种形式，可以表示为具有有限字母的有限句子（与所描述的语言相同的字母，加上几个额外的符号）。[注 1] 所以可能的 Type 0 文法的数量是可数无限的，文法集和语言集之间不存在对应关系。

然而。不存在生成语法的语言（即集合）的存在并不一定意味着存在比生成语法“更具表现力”的其他方式来描述这些语言。任何可以使用有限字母表写成有限字符串的描述只能描述可数的无穷集合。是否相同的可数无穷大取决于形式，并且通常不会有可以证明同态的算法。但是一些等价是已知的（例如与图灵机的等价，这是一个特别有趣的等价）。

所以，我们有一个有趣的小难题，它（当然）与哥德尔的不完备性定理有关。也就是说，无论我们使用什么系统来描述一种语言，语言都比描述语言的方式多。所以问题是“我们如何描述一种没有可用描述的语言？” 没有一个好的答案（如果我们通过调用某个集合“Sue”来回答它，那么仍然会有无数个不存在名称的可能集合）。

虽然所有这些无限的探索都很有趣，但它有一些问题：

  1. 它与编程几乎没有关系（如果有的话），因此它是否是 StackOverflow 的主题值得怀疑。

  2. Kurt Gödel 和 Georg Cantor 这两位数学家负责这个答案中的大部分概念，他们都患有严重的抑郁症。只是说。

笔记

  1. 尽管乍一看，Type 0 语法的字母表可能比所描述语言的字母表任意大，但实际上并非如此。语法的字母表由目标字母表加上一组有限的非终结符加上一个→符号组成；可以使用任何方便的基数（例如二进制）来编写非终结符。所以只需要三个额外的符号（你可以通过任意指定一个非终端数字作为箭头将其减少到两个）。（看起来您似乎需要第三个符号来分隔非终结符的名称，但您可以使用斐波那契编码来生成始终以 1 开头且从不包含两个 1 的代码，这样您就可以在开始明确地标记符号的开始。）
于 2020-07-12T23:39:50.680 回答