Countable 字符串总是 Countable 吗？
Can Countable string is Countable always?
- 为什么有的集合可数，有的不可数？说正则集是可数的，但 (0+1)* 怎么会是可数的呢？是一个无穷大的串，怎么可能是可数集呢？
- 从N到N的所有非递减函数的集合如何可数？
- N的所有有限划分的集合怎么是不可数的？
首先让我们澄清一个常见的误解：(0+1)* 不是无限字符串。它是一种无限数量的有限字符串的语言。区别很重要：语言中的任何给定字符串都是有限的，但它们的数量是无限的。
L=(0+1)*表示L={'', '0', '1', '00', '01', '10', '11', etc}。这也说明了一种语言如何被认为是可数的，如果你列出所有长度为 0、1、2 等的单词。语言中的每个单词在这个集合中都有一个位置，并且可以映射到自然数。
所有常规语言都是可数词集。有限语言是平凡可数的。无限种语言是可数的，因为可以遍历相应的DFA，有序枚举整个语言，让所有的字符串都映射到自然数。
另外两个问题更笼统地是数学问题，而不是计算机科学问题。这应该有所帮助：https://math.stackexchange.com/questions/1396896/number-of-non-decreasing-functions. For the last question, this might help: https://en.wikipedia.org/wiki/Cantor%27s_theorem
- 为什么有的集合可数，有的不可数？说正则集是可数的，但 (0+1)* 怎么会是可数的呢？是一个无穷大的串，怎么可能是可数集呢？
- 从N到N的所有非递减函数的集合如何可数？
- N的所有有限划分的集合怎么是不可数的？
首先让我们澄清一个常见的误解：(0+1)* 不是无限字符串。它是一种无限数量的有限字符串的语言。区别很重要：语言中的任何给定字符串都是有限的，但它们的数量是无限的。
L=(0+1)*表示L={'', '0', '1', '00', '01', '10', '11', etc}。这也说明了一种语言如何被认为是可数的，如果你列出所有长度为 0、1、2 等的单词。语言中的每个单词在这个集合中都有一个位置，并且可以映射到自然数。
所有常规语言都是可数词集。有限语言是平凡可数的。无限种语言是可数的，因为可以遍历相应的DFA，有序枚举整个语言，让所有的字符串都映射到自然数。
另外两个问题更笼统地是数学问题，而不是计算机科学问题。这应该有所帮助：https://math.stackexchange.com/questions/1396896/number-of-non-decreasing-functions. For the last question, this might help: https://en.wikipedia.org/wiki/Cantor%27s_theorem