问题标签 [turing-machines]

我必须确定一种语言（例如 L={a^nb^mc^s | 0<=n<=m<=s}）是否是常规的、上下文无关的、递归的、递归可枚举的，或者它们都不是。

我知道如何确定一种语言是正则的（找到一个有效的 DFA 或正则表达式）还是上下文无关的（找到一个有效的 PDA 或上下文无关的语法）；我知道递归语言有一个总是停止的图灵机，而递归可枚举语言有一个可能不会停止的图灵机。

所以问题是：是否有一个快速的标准来确定语言是递归的还是递归可枚举的，或者两者都不是？例如，我不必构建一个 PDA 来理解一种语言是上下文无关的，我看不到它需要一个堆栈的事实；是否有类似的快速解决问题的方法（希望可以省去构建图灵机的麻烦）？

在亚马逊上阅读 Stephen Wolfram 的“A New Kind of Science”的评论时，我发现了以下声明：

每个计算机科学 (CS) 学生都知道 dovetailer，这是一个非常简单的 2 行程序，它系统地列出并执行通用计算机（例如图灵机 (TM)）的所有可能程序。

有人可以给出一个“简单的两行程序”来说明“鸽派”吗？

请给我一些关于如何去做的想法

画一个图灵机（使用 Sipser 表示法），它至少有 4 个非平凡（即非拒绝）状态和至少 6 个非平凡（即，非拒绝状态）转换。

我得到了一个正则表达式，我想将其转换为 NFA，然后是 DFA。这是正则表达式：

a ( b | c )* a | aac* b

然后我使用汤姆森算法将其转换为 NFA：

这是DFA：

有人可以快速看一下让我知道我是错还是对？

我试图最小化这个 DFA：http: //img145.imageshack.us/img145/3006/dfac.png

这是我最小化的 DFA：http: //img195.imageshack.us/img195/4131/mdfa.png

我对么？谢谢

PS-这是作业。我们可以讨论家庭作业。我不是在问答案，我只是想知道我是否走在正确的轨道上，因为这是我第一次处理状态机。

语言 L = {1^200}，或者更确切地说，连续有 200 个 1 的语言？Aka，这个 TM 只有在连续收到 200 个 '1' 时才接受。因此需要 200 个状态来解决这个问题，还是可以用更少的状态来简化？

我要求这个来帮助理解 TM 的工作原理。

注意：字母表只是 {1}。TM 可以使用任意数量的磁带。

如果我有一个上下文无关语法 G 使得 G 的语言为零，那么 G 是可判定的吗？

我知道答案是肯定的，但我无法证明这一点。我的第一个想法是说只有一个状态 q1，它是相当于 G 的图灵机的启动状态和接受状态。这台机器将不接受任何输入并立即停止并接受，因为它已达到接受状态状态。这是一个可以接受的答案，还是我离开这里？

编辑：

正如乔尔在下面所说，我描述的语言接受所有字符串。为了解决这个问题，我建议使用第二台机器 G'。G' 有 3 个状态，开始状态 q1、接受状态 q2 和拒绝状态 q3。q1 在 G' 字母表中的所有符号上都转换为 q3，q2 也是如此。q1 有一个到 q2 的 epsilon 转换。因此，如果提供给 G' 的字符串中存在任何符号，则 G' 将拒绝。如果没有符号，唯一的选择是将 epsilon 转换为接受状态。听起来怎么样？

编辑：

上面的解决方案被证明可以接受语言 L(G') = {""}。

我有一个关于车床的非常简单的问题。

如果它采取的第一个动作包括倒带，它会移回起点，还是这是一种特殊情况，它会保持在起点？

很容易找到用 (Φ) 代替两端字母的回文。

可以将 a 更改为 A ，并在任务结束时将 A 更改为 a 。但是有人知道如何在不使用其他标志的情况下实现这一目标吗？

我在 JFLAP 中构建的图灵机是一个二进制加法器。这是一个 3 磁带 TM：前两个磁带是输入，第三个磁带得到输出。当我尝试进行批量测试（在此处找到信息）时，我无法让 .txt 文件中的第三个字符串成为输出磁带。我的 .txt 文件的构建方式如下：

但是，因为它是一个 3 磁带机，而且它必须是，我想成为输出字符串的最后一个二进制字符串被作为第三个输入字符串，对于所有测试，它应该是空白的。有什么方法可以格式化我的测试字符串，以便 JFLAP 理解最后一个字符串应该是输出？