问题标签 [turing-machines]

我有一个任务，我需要拍摄一些现有的照片[显示一些自动机（DFA、NFA、图灵机）]，并以某种方式将它们转换为一种格式，这使我能够使用数据将其表示为自动机以及将其编译成一些图形表示。你们中有人做过类似的事情吗？是否有任何 Python 库/框架可以让我以图形方式呈现一些自动机数据？

我有一个字符序列 xxxxxx（x^k 和 k > 0）我的目标是将这句话转换成荷兰国旗，也就是说：

xxxxx -> RRWWBB xxxx -> RWBB

R <= W <= B

我发现的所有解决方案都具有非常高的复杂性。您是否有任何提示/线索可以帮助我仅使用一个磁带和一个磁头/光标来构建图灵机？

我花了整整一个月的时间来解决这个问题，因为我是从练习一书中得到的，我很想知道如何在图灵机上写这个；我真的很想学这个。请问有人可以提供帮助吗？

考虑您登录的最后两个字母（如果两个字母相同，请选择拉丁字母中的下一个字母作为您的第二个符号）。编写一个能够识别语言 Stretch(x+1) 的图灵机。这是所有字符串的语言，这些字符串包含两个字母的连续出现字符串，后跟“*”，然后是另一个字母字符串，其中每个字母出现 x+1 次，其中第一个字符串中出现了一次的字母。这里，x = 1。机器的输入是 a、b、* 的非空字符串。例如，如果字母是“a”和“b”（并且 x=1），则 aba*aabbaa、bb*bbbb 和 baab*bbaaaabb 在该语言中，但 abb*abbb 不是。

如果您能帮助我，我将不胜感激。

AFAIK，图灵可计算数字是图灵机可以返回第 i 个索引的数字。所以一个不可计算的数字就像一个数字，如果其他程序在其他一些输入上停止等等，它的小数点就被确定了。但话又说回来，PI 是一个实数，它不能被 TM 枚举，因此不能被计算？那么哪个学派是正确的呢？

例如，如果我在输入的末尾并且我正在向左移动，我怎么知道我在磁带的开头？如果还有更多 |_| 在输入之前，我很容易告诉我又在开始，但我不知道是否有。这不是一个家庭作业问题，我相信答案是显而易见的，这就是为什么我在网上找不到关于输入左侧磁带的任何信息。谢谢。

字母：a、b、c 我正在尝试定义一个接受

我认为可以接受的一些字符串是：#abc#; #aabbcc#; #aaabbbccc#; #abbccc#; #aaabbc# 等 a、b 和 c 的数量不一定相等。

在最右边的黑色空间上启动下推自动机的头部。

通常我把我的 PDA 写成列：

等等...

字母表：0、1

考虑一个翻转，翻转每个字符：0 -> 1；1 -> 0 所以如果 w = 0011 那么 w-flip = 1100

考虑反向是颠倒顺序的字符所以如果 w = 01101 那么 w-reverse = 10110

现在我正在尝试制作一个 PDA，它采用字符串 w，然后打印 w，打印（w-flip-reversed）

所以这将打印：“011001”

考虑 # 是一个空白字符。所以一个字符串会开始 #011#

转换表如下所示：

等等

有任何想法吗？

我应该为语言 0^k1^k (k>=0) 绘制一个枚举器。我不确定这与为该语言构建图灵机状态图有何不同：我理解它的方式是，我需要构建一个枚举器，通过模拟图灵，在给定所有高于 {0,1} 的字符串的情况下，我需要构建一个能够识别上述语言的枚举器机器在 i 步骤中识别字符串 i 上的这种语言，我想不出如何使用状态图来做到这一点，但我的老师指出，这就是我们如何证明枚举器和图灵机之间的等价性，所以我认为我们必须做的是使用为枚举器定义的转换函数，这使得图表看起来类似于识别 0^k1^k 的图灵机，只是我们没有移动到 qaccept，而是移动到 qprint 以获取语言中的输入，然后对于必须拒绝的输入，我们打印 epsilon? 但是我们如何在字母表 {0,1} 之上产生无限数量的字符串呢？在初始状态，工作带和打印带是空的。有人可以为我澄清这些观点吗？也许我误解了。

图灵机可以考虑空间（磁带上的内存空间）和时间的复杂性。

有诸如 PSPACE 和 EXPSPACE 之类的类。

此外，我们可以提出肯定存在于 PSPACE 中的算法。

http://www.springerlink.com/content/3hqtq11mqjbqfj2g/

但是，当我实际编写程序时，有些程序比其他程序运行得更快，有些程序的内存 (RAM) 占用空间比其他程序小。

大概如果我编写一个 PSPACE 算法来解决问题 X 和一个 EXPSPACE 算法来解决同样的问题，那么 EXPSPACE 程序应该比 PSPACE 代码使用更多的 RAM。

有没有办法根据起始算法的理论评级来估计将涉及多少 RAM？

你知道任何实现图灵机和有限状态自动机等抽象机器的编程语言吗？

也就是说，处理以下输入：

• 一个 5 元组（来自形式语言 101 的臭名昭著的 ⟨Q,Σ,δ,q0,F⟩），一个用于图灵机的7 元组或抽象机器的任何其他形式表示。
• 一个输入词。

并告诉我输入的词是否是接受词。

谢谢，

亚当