2回答
图灵机
、、
我正在读一本关于语言和自动机的书，我不理解图灵机。我已经自学了DFA的NFA和下推自动机，没有任何问题。有人能解释一下这是怎么回事吗？B= {w#w|w∈{0，1}*}
非常感谢！
浏览 2提问于2013-04-10得票数 1
回答已采纳
设{w#w |w∈{0,1}*}为车床的语言。例如，它将接受01#01。 但是，如果我们有一台接受{w#w |w∈{0,1}}语言的车床。它将接受什么字符串？
浏览 48提问于2020-12-07得票数 0
1回答
递归集或不递归集
、、、
有没有人可以帮助我说，我怎样才能证明下面提到的两种语言是可判定的或不可判定的？ 在输入w上，图灵机M从不向左移动读/写头，其中w∈{0，1}∗L1:= M∈{0，1}∗。在输入w上，图灵机M在每个步骤中移动读/写头，其中w∈{0，1}∗和M∈{0，1}∗。
浏览 38提问于2021-01-08得票数 1
回答已采纳
我必须使用两卷带的图灵机来决定w#w。我知道你需要把最后一个部分，也就是#后面的部分复制到第二盘磁带上，然后逐个字符地比较，看看这两个部分是否相同。
我的问题是如何将#后面的部分复制到第二盘磁带上？W= (a|b)^*
浏览 1提问于2012-02-21得票数 0
回答已采纳
我得弄清楚这种语言
可以由图灵机判断。TM有一个磁带和两个头/指针。输入字符串是有限的。对如何解决这个问题有什么建议吗？
浏览 3提问于2015-01-15得票数 0
回答已采纳
3回答
我应该为语言0^k1^k (k>=0)绘制一个枚举器。我不确定这与为这种语言构建图灵机状态图有什么不同:我理解的方式是，我需要构建一个枚举器，它可以在给定{0,1}以上的所有字符串的情况下，通过模拟图灵机在字符串i上识别i步上的语言来识别上述语言，但我的老师指出，这就是我们如何证明枚举器和图灵机之间的等价性，所以我认为我们必须做的是使用为枚举器定义的转换函数，使图看起来类似于识别0^k1^k的图灵机，只是我们不是移到qaccep
浏览 3提问于2010-11-15得票数 2
如何证明/否定语言{⟨A，⟩，⟩，A是NFA，L(A)={0,1}∗}是/不可判定的？
我最初认为，因为它涉及到NFA，所以它是可判定的，但是由于没有输入字符串来模拟这种变化吗？我想不出有一台图灵机器能决定这一切。由于{0，1}*理论上是无限的，是否意味着图灵机永远不会停止，因此语言是不可判定的？如果是这样的话，我该如何证明呢？
浏览 0提问于2018-03-02得票数 1
回答已采纳
我目前就读于我校计算机理论的本科版本，我们正在讨论下推自动机、图灵机和丘奇图灵论文。为语言{wwR \ w∈{0,1}*}构造PDA。例如，存在一个不确定的PDA识别以下语言，但没有确定性PDA能够识别这种语言：
所以，我的问题是，是否有可能写这个确定性的PDA？
浏览 6提问于2022-10-04得票数 0
1回答
我有一个可能无限的N*N矩阵，可以由一些任意编程语言使用。在这种编程语言中，矩阵的每个字段都包含一个整数(从零到无穷大)。在这种编程语言中，我们只能通过在其中一个轴上移动一步，然后读取当前值来访问该数组的字段。当前字段的值也可以递增或递减。现在我的问题是整数应该如何存储在磁带上。我不能为每个数字指定一定数量的“位”，因为最大值是没有限制的。我也不确定最终的图灵机将如何有效地访问
浏览 3提问于2019-12-15得票数 1
1回答
如何用约简方法证明语言的长度除以2？L={ L=是一个图灵机，其中的l(M)|=0 mod 2}2)采用不停机的约简方法，图灵机拒绝任何输入，图灵机的长度为0，满足上述条件！
浏览 0提问于2015-12-07得票数 1
回答已采纳
从许多关于可计算性的教科书中，我看到了我们如何定义等效图灵机如下：其中L( TM1 )是TM1引用的语言，即L(TM1) = {w\ TM1(w) = accept}，L(TM2)也是。我的问题是:为什么上面的定义完全忽略了“被拒绝的语言”{w why TM1(w) = reject}，而‘循环语言’{w\x TM1(w</e
浏览 6提问于2022-11-02得票数 1
1回答
绘制决定语言的双磁带非确定性图灵机M的图如果我能得到帮助解释如何构造NDTM (语言)的步骤，我相信我可以画出图表，但我无法给出一个答案。
谢谢
浏览 1提问于2017-01-09得票数 0
回答已采纳
1回答
在证明中，我们必须向图灵机提供程序的副本和输入的副本，以确定该程序是否在输入时停止。在矛盾中，为什么必须是程序作为程序和输入？如果这听起来令人困惑，我很抱歉。
浏览 2提问于2016-12-07得票数 1
我需要证明L= {w|M_w接受1x当且仅当它接受0x}不是递归的
我相信这应该是赖斯定理的一个简单应用，即对于递归可枚举语言的任何非平凡性质P，{w | M_w是图灵机，L(M_w)在P中}不是递归的我对此有点不确定，因为我不太确定什么是属性；此外，我也不知道如何证明它是递归枚举语言的一个属性。
浏览 0提问于2019-04-08得票数 1
1回答
证明半可译语言
、、
我必须证明“半可译语言是由直接的态射运算关闭的”。
我认为E到F的一个直接态射是一对态射s: e -> F，p: F->E，其中p·s= IdE。所以我的porposal是用图灵机器来证明的，因为图灵可识别的语言在∪，°，*和∩下是封闭的，但是我不知道如何用TM中运行的特定语言来证明它(如果我的提议是正确的)。
浏览 6提问于2017-04-26得票数 0
回答已采纳
1回答
我读了很多答案，如果一种语言不是上下文无关的，那么它的补语就是上下文无关的(如果我错了，请纠正我)。对于相反的情况是真的吗？上下文无关语言的补语是上下文无关的吗？
浏览 15提问于2015-12-13得票数 0
回答已采纳
“首先，我们表明，如果我们有一个枚举数E枚举语言A，一个TM M识别A，TM M的工作方式如下。
如果w没有出现在E的输出中，它就不会出现在E的列表中。他要说什么？
浏览 2提问于2015-08-06得票数 2
回答已采纳
1回答
我使用的教科书“正式语言和自动机导论”，第6版，彼得林茨。接受和终止不同的概念吗？或者是否有一个例子，它到达qf，但没有停止？谢谢。
浏览 5提问于2022-03-25得票数 0
扫码
添加站长 进交流群
领取专属 10元无门槛券
手把手带您无忧上云
相关资讯
热门标签
云服务器
ICP备案
腾讯会议
云直播
对象存储活动推荐
腾讯云开发者
