证明了一组有限语言与有限字母表中的所有语言都可以是可数/不可数的

Question

我遇到了以下事实：

1. 在有限字母表上的一组有限语言是可计算的。
2. 在有限字母表中的一组语言是不可数的。
   我相信这一点的证据将类似于以下事实3.
3. {0,1}的语言组是不可数的。

我遇到了事实证明1 这里事实上3 这里。

事实摘要1证明：

让您的有限字母表为 $σ= {a_1，...，a_ℓ} $ ，并让 $ \＃$ < / span>是某种字符不在 $Σ$ 。让 $ l= {w_1，...，w_n} $ 是 $Σ$ 的有限语言。然后字符串 $ \＃w_1 \＃w_2 \＃... \ #w_n $ 映射不同 $ l $ 到不同的整数。

事实上摘要3校验：

let $ l $ 设置为 $ \ {0,1 \} $ 。我们可以从 $ l $ 到 $ \ mathbb {n} $ ，生成一对一的映射：只需在W中的每个字符串前面添加一个1，并将生成的字符串解释为二进制数。所以<跨越类=“math-container”> $ l $ 是可计算的。现在让 $ l _ {\ {\ {0,1 \}} $ 是可计算的，其中 $ l \ {0,1 \ }=\ {l_1，l_2，l_3，... \} $ 使用每个 $ l_i $ 作为 $ \ {0,1 \} $ 。鉴于每个 $ l_i $ 是一个集合，其元素来自 $ l $ ，并且 $ l $ 是可计算的，我们可以构建一个表，其行索引是语言指标，其列索引如下所示：对于带有行索引的每个表单元格 $ i $ 和列索引 $ j $ ，写1如果语言 $ l_i $ 包含字符串 $ s_j $ 或0否则。

我们将每个对角线单元的值翻转上表上的每个对角线单元的值，然后收集所有字符串 $ s_j $ ，使得 $ S_J $ 翻转后有一个1：
让我们称之为 $ l_ {diag}= {s_2，s_3，...} $ 。
$ l_ {dig} $ 是一种具有特殊属性的语言：它与每种语言 $l_i∈l_ {\不同{0,1 \}} $ 。这意味着 $ l_ {diag}≠l_i $ 所有 $l_i∈l$ {{0,1因此， $ l_ {diag}∉l_ {\ {0,1 \}} $ 。但是，由于<跨度类=“math-container”> $ l $ 是一组字符串，它位于 $ l $ ， $ l_ {dig} $ 是一种{0,1}的语言，因此 $ l_ {dig}∈l_ {\ {0,1 $ ，一个矛盾。因此 $ l _ {\ {0,1 \}} $ 不能可计算。

怀疑

我得到了所有证据，但我不明白为什么他们中每个人的方法都不能用来证明其他事实不正确。那是：

1. 为什么我无法使用事实上的证明方法3事实3是不正确的，即“超过{0,1}的语言集合”。 无法形成类似的字符串 $ \＃w_1 \＃w_2 \＃... \ #w_n $ 为不同的语言映射到不同的整数？

2. 为什么我无法使用3证明方法来证明事实1是不正确的，即“在有限字母表上设置有限语言是不可数的”？

   我无法为有限语言表达类似的表，然后表单 $ l_ {dig} $ 哪个不属于一组有限语言？

Answer 1

1. 如果语言是无限的，则单词 $ \＃w_1 \＃w_2 \ ldots $ 是无限的，因此不会映射到一个以任何有意义的方式整数。

2. 应用于所有有限语言集的对角角参数可能（实际上，将）导致无限的语言。