有没有有限单词的有限语言？

Question

在那儿 需要 对于$ l subseteq sigma^*$ 无穷 不确定？

我的意思是，如果我们选择一种语言$ l'$为a 有限版本的有限版本 $ l subseteq sigma^*$，即$ | l'| leq n $，（$ n in mathbb {n} $），带有$ l' subset l $。 $ l'$成为一种不可证明的语言吗？

我发现存在一个问题：“如何选择$ n $ n $ n in $ l''$ n $ n $的问题，我们必须为选择一个规则来选择哪个是$ l'的第一个$ n $元素$，一种“有限”的克莱恩星星操作。目的是在不需要无限集的情况下找到不可证明的语言，但我看不到。

编辑注意：

尽管我选择了答案，但许多答案 和所有评论 是重要的。

Answer 1

是的，为了不确定，需要无限的$ l $。

为了加起来Raphael和Sam的答案，您应该考虑“可决定”，就像计算机程序可以解决的问题一样。所需的程序非常简单，它只需要为$ l $中的元素输出“是”，或者说否。

因此，“复杂” $ l $的是，您需要编写的程序的时间越长。换句话说，您运行的程序越长，您可以检查更多内容...因此，如果有人给出有限的语言$ L $，例如$ l = {a_1，a_2， ldots，a_n } $，您可以编写以下程序：

if INPUT = $a_1$ output Yes;
if INPUT = $a_2$ output Yes;
...
if INPUT = $a_n$ output Yes;
output No;

现在，如果有人给您较大的$ L $（但有限），那么您只需编写一个更长的程序即可。这始终是正确的，任何有限的$ l $都将拥有自己的程序。唯一的“有趣”情况是当$ l $是无限的时候会发生什么 - 您的程序 不能 无限。

“不可证明性”的问题更加有趣：它的（无限）$ l $没有适合他们的程序。我们知道，这种语言必须存在，因为有限（但无限）长度的程序数量（无限）语言$ l $要多。

Answer 2

我不确定我是否正确理解这个问题，但是每种有限语言都是常规的。没有普通语言是不可决定的，因此没有有限的语言是不可决定的。所有这些陈述都是众所周知的，可以在 霍普克罗夫特和乌尔曼.

Answer 3

如果您的语言$ l'$是有限的，则可以执行 桌子查找 在一个装有$ l'$中所有单词的硬编码表上。将其写入图灵机很尴尬，但在其他相同的模型中，这很明显。

实际上，有限的自动机就足够了。为$ l'U构建一个自动机，如下：

1. 对于L'$中的每一个$ W ，创建一个接受$ W $的状态的线性链。
2. 创建一个新的初始状态$ q_0 $。
3. 将$ q_0 $连接到1. $ varepsilon $ - 运输的所有自动机的初始状态。

如此构造的自动机显然接受$ l'$。因此，$ l'us $是常规的，因此可计算（由$ mathrm {reg} subsetneq mathrm {re} $）。

请注意，某些推理适用 联合会 $ l'$，即$ big | edline {l'} big | < infty $;您只需编码元素 不是 在$ l'$中。

Answer 4

要变得有趣（为了思考可计算性），决策问题必须具有无限的许多“是”答案和无限的“否”答案。此类决策问题与语言完全相对应，其字母上包含许多字符串，并且在其字母上也将无限的许多字符串排除在外。

其他任何内容都可以在只有有限的信息中编码（最坏的情况下，只是在语言中或不使用语言中的大量字符串），因此可以通过简单的DFA /正则表达式来计算。我希望应该很明显的是，对于任何有限的字符串列表，您都可以立即写下一个正则表达式，简单地说明所有字符串。

我的计算理论讲师的智慧是“上帝存在？”的问题是可以计算 - 它是由立即接受的机器计算的，要么是立即拒绝的机器；我们只是不知道哪一个！