如何定义一种不符合乔姆斯基层次结构的语言？
How can one define a language which does not fit in the Chomsky Hierarchy?
我问这个问题是因为我偶然发现了 Chomsky Language Types
的公认答案
这句话是指 Type-0 文法：
This means that if you have a language that is more expressive than
this type (e.g. English), you cannot write an algorithm that can list
each an every (and only these) words of the language
据我所知：
- 没有关于英语是什么的数学描述，因此争论英语在形式语言层次结构中的位置是没有意义的。
- 如果有，那么英语肯定会被某种 0 型语法识别，因为它是由有限数量的推理定义的——它可以是公理、语法，任何东西。 （如果不是 - 如果不是通过有限的步骤，有人怎么能定义它呢？）
因此：
- 我们不能开始谈论 'expressive' 语法需要如何才能精确地 未知的数学对象
因此我的问题：
- 如何定义一种不符合乔姆斯基层次结构的语言？
- 如果 (?) 数学家需要 有限 步来定义
集合的基数不会使它们递归可枚举 - 那么必须存在比 Type-0 更具表现力的语法，因为它们（数学家）遵循有限数量的规则（如果你愿意的话，产生规则）来产生非 RE 集。他们在哪里？
语言是用某些有限字母表书写的可能无限的有限单词集。由于字母表是有限的，每个单词的长度也是有限的，因此在存在枚举的意义上，任何语言的单词都是可枚举的。换句话说，任何语言的大小至多是无限的。
但是，由于字母表的 Kleene 闭包的任何子集都是一种语言，因此语言的数量不是可数无限的。因此，没有语言的枚举。
乔姆斯基层次结构基于一种形式主义，它可以表示为带有有限字母表的有限句子（与所描述的语言相同的字母表，加上几个额外的符号）。 [注1]所以可能的Type 0文法的数量是可数无限的，并且文法集和语言集之间不可能存在对应关系。
不过。不存在生成语法的语言（即集合）的存在并不一定意味着存在比生成语法“更具表现力”的其他描述这些语言的方式。 任何可以使用有限字母表写成有限字符串的描述只能描述可数的无穷集合。是否是同一个可数无穷大取决于形式主义，一般不会有算法可以证明同态。但是有些等价是已知的（比如与图灵机的等价，这是一个特别有趣的等价）
所以，我们有一个有趣的小难题，它（当然）与哥德尔不完备性定理有关。也就是说，无论我们使用什么系统来描述语言，语言的数量都多于描述语言的方式。所以问题“我们如何描述一种没有可用描述的语言？”没有一个好的答案（如果我们通过调用一些集合“Sue”来回答它，那么仍然会有无数的可能集合没有名字存在）。
尽管无限觅食很有趣，但也存在一些问题：
它与编程几乎没有关系（如果有的话），因此它是否是 Whosebug 的主题值得怀疑。
Kurt Gödel 和 Georg Cantor 这两位负责此答案中大部分概念的数学家都患有严重的抑郁症。随便说说。
备注
- 虽然乍一看似乎 0 型语法的字母表可能比所描述语言的字母表任意大，但实际上并非如此。语法的字母表由目标字母表加上一组有限的非终结符加上一个 → 符号组成；可以使用任何方便的基数（例如二进制）的数字来编写非终结符。因此只需要三个额外的符号（您可以通过任意指定一个非终端数字作为箭头来将其减少到两个）。 （看起来你需要第三个符号来分隔非终结符的名称，但你可以使用斐波那契编码来生成始终以 1 开头并且从不包含两个 1 的代码，这样你就可以在开始明确标记符号的开始。）
我问这个问题是因为我偶然发现了 Chomsky Language Types
的公认答案这句话是指 Type-0 文法：
This means that if you have a language that is more expressive than this type (e.g. English), you cannot write an algorithm that can list each an every (and only these) words of the language
据我所知：
- 没有关于英语是什么的数学描述，因此争论英语在形式语言层次结构中的位置是没有意义的。
- 如果有，那么英语肯定会被某种 0 型语法识别，因为它是由有限数量的推理定义的——它可以是公理、语法，任何东西。 （如果不是 - 如果不是通过有限的步骤，有人怎么能定义它呢？）
因此：
- 我们不能开始谈论 'expressive' 语法需要如何才能精确地 未知的数学对象
因此我的问题：
- 如何定义一种不符合乔姆斯基层次结构的语言？
- 如果 (?) 数学家需要 有限 步来定义 集合的基数不会使它们递归可枚举 - 那么必须存在比 Type-0 更具表现力的语法，因为它们（数学家）遵循有限数量的规则（如果你愿意的话，产生规则）来产生非 RE 集。他们在哪里？
语言是用某些有限字母表书写的可能无限的有限单词集。由于字母表是有限的，每个单词的长度也是有限的，因此在存在枚举的意义上，任何语言的单词都是可枚举的。换句话说，任何语言的大小至多是无限的。
但是，由于字母表的 Kleene 闭包的任何子集都是一种语言，因此语言的数量不是可数无限的。因此，没有语言的枚举。
乔姆斯基层次结构基于一种形式主义，它可以表示为带有有限字母表的有限句子（与所描述的语言相同的字母表，加上几个额外的符号）。 [注1]所以可能的Type 0文法的数量是可数无限的，并且文法集和语言集之间不可能存在对应关系。
不过。不存在生成语法的语言（即集合）的存在并不一定意味着存在比生成语法“更具表现力”的其他描述这些语言的方式。 任何可以使用有限字母表写成有限字符串的描述只能描述可数的无穷集合。是否是同一个可数无穷大取决于形式主义，一般不会有算法可以证明同态。但是有些等价是已知的（比如与图灵机的等价，这是一个特别有趣的等价）
所以，我们有一个有趣的小难题，它（当然）与哥德尔不完备性定理有关。也就是说，无论我们使用什么系统来描述语言，语言的数量都多于描述语言的方式。所以问题“我们如何描述一种没有可用描述的语言？”没有一个好的答案（如果我们通过调用一些集合“Sue”来回答它，那么仍然会有无数的可能集合没有名字存在）。
尽管无限觅食很有趣，但也存在一些问题：
它与编程几乎没有关系（如果有的话），因此它是否是 Whosebug 的主题值得怀疑。
Kurt Gödel 和 Georg Cantor 这两位负责此答案中大部分概念的数学家都患有严重的抑郁症。随便说说。
备注
- 虽然乍一看似乎 0 型语法的字母表可能比所描述语言的字母表任意大，但实际上并非如此。语法的字母表由目标字母表加上一组有限的非终结符加上一个 → 符号组成；可以使用任何方便的基数（例如二进制）的数字来编写非终结符。因此只需要三个额外的符号（您可以通过任意指定一个非终端数字作为箭头来将其减少到两个）。 （看起来你需要第三个符号来分隔非终结符的名称，但你可以使用斐波那契编码来生成始终以 1 开头并且从不包含两个 1 的代码，这样你就可以在开始明确标记符号的开始。）