腾讯云
开发者社区
文档
建议反馈
控制台
首页
学习
活动
专区
工具
TVP
最新优惠活动
文章/答案/技术大牛
搜索
搜索
关闭
发布
登录/注册
精选内容/技术社群/优惠产品,
尽在小程序
立即前往
文章
问答
(9999+)
视频
沙龙
1
回答
这种
语言
可以分辨吗?
math
、
theory
、
primes
、
turing-machines
、
decidable
我在纠结于这是否是可
判定
的
:我倾向于认为,这是可
判定
的
,因为当输入图灵机时,它将永远不会达到接受状态和无限大
的
循环,除非它拒绝然而,我也知道,要想判断一种
语言
,就必须有一个算法来决定它;我们不一定要知道它是如何完成
的
。有了这个,我觉得它是可以决定
的
吗?有人知道怎么证明吗?
浏览 12
提问于2012-01-26
得票数 3
1
回答
证明这种
语言
是否是可分辨
的
和可识别的
computation-theory
、
turing-machines
、
formal-languages
、
decidable
如果L1和L2是
语言
,我们就有了一种新
的
语言
我如何证明INTERLACE是: 可辨认
的
?我知道如何表达这种
语言
是正常
的
。我不太确定..。以下是我
的<
浏览 0
提问于2017-04-01
得票数 5
回答已采纳
1
回答
图灵机可
判定
性模糊案例
turing-machines
、
decidable
、
undecidable-instances
1)是一个图灵机M,它接受
语言
L= {ε},不接受输入?同样
的
想法,凭直觉我会说是的,因为可
判定
性
的
定义,但我不知道,有些事情困扰着我。 3)回文
的
语言
,无论是哪种
语言
,都是可
判定
的
吗?对于这
浏览 8
提问于2017-11-24
得票数 1
回答已采纳
1
回答
证明输入x}
的
语言
L= {w∈{0,1}∗Mw(x)↓是部分可
判定
但不可
判定
的
computability
我试图证明输入x}
的
语言
L= {w∈{0,1}∗Mw(x)↓是部分可
判定
的
,但不是可
判定
的
。Mw是M
的
编码,因此L
语言
使机器M
的
所有编码在某个输入x上停止。我有两个想法: 但是,我很难决
浏览 2
提问于2018-10-30
得票数 1
5
回答
递归
语言
与上下文敏感
语言
formal-languages
、
context-sensitive-grammar
、
chomsky-hierarchy
在乔姆斯基
的
层次结构中,没有定义递归
语言
集。我知道递归
语言
是递归枚举
语言
的
子集,并且所有递归
语言
都是可
判定
的
。 我感兴趣
的
是递归
语言
与上下文敏感
语言
的
比较。我是否可以假设上下文敏感
语言
是递归
语言
的
严格子集,因此所有上下文敏感
语言
都是可
判定
的
?
浏览 27
提问于2010-06-17
得票数 6
3
回答
为什么递归枚举
语言
不能确定
computer-science
、
turing-machines
、
formal-languages
这是维基百科中可
判定
的
定义。 递归集是可递归枚举集
的
子集。有一些递归枚举
语言
在递归集之外。那么,为什么递归枚
浏览 3
提问于2012-02-26
得票数 5
回答已采纳
1
回答
两种图灵可
判定
语言
的
交集是图灵可
判定
的
algorithm
、
proof
、
turing-machines
证明两种图灵可
判定
语言
的
交集是图灵可
判定
的
。(给定决定每种
语言
的
算法,描述确定字符串是否属于交集
的
算法。) 我知道,如果有一种算法来决定成员资格,一种
语言
是图灵可决定
的
。
浏览 1
提问于2015-12-06
得票数 1
1
回答
克莱恩星无法分辨
computer-science
、
complexity-theory
、
computation-theory
、
turing-machines
我知道,如果L是可
判定
的
,我们可以通过构造一个图灵机来证明L*也是可
判定
的
,但是我很难解决这个问题:如果L是不可
判定
的
,那么L*也是不可
判定
的
。这句话是真的还是假
的
?
浏览 2
提问于2017-10-03
得票数 1
1
回答
如果G是上下文无关
语言
,那么L(G) = (sigma) *是可
判定
的
还是不可
判定
的
?
context-free-grammar
如果G是上下文无关
语言
,那么L(G) = (sigma) *是可
判定
的
还是不可
判定
的
?我从哪里得到这个问题
的
来源是,答案是undecidable...but,我认为它是可决定
的
,因为:由于sigma *是无限
的
(如果我错了,请纠正我),并且上下文无关
语言
的
无穷性是可决定
的
,所以上述是无限上下文无关
语言
,我认为它是可决定
的
……
浏览 0
提问于2019-12-06
得票数 1
2
回答
语言
{⟨A⟩⟩A是NFA和L(A)={0,1}∗}可
判定
吗?可
判定
的
?
computer-science
、
turing-machines
、
decidable
如何证明/否定
语言
{⟨A,⟩,⟩,A是NFA,L(A)={0,1}∗}是/不可
判定
的
? 我最初认为,因为它涉及到NFA,所以它是可
判定
的
,但是由于没有输入字符串来模拟这种变化吗?如果是这样的话,是怎么做
的
?我想不出有一台图灵机器能决定这一切。由于{0,1}*理论上是无限
的
,是否意味着图灵机永远不会停止,因此
语言
是不可
判定
的
?如果是这样的话,我该如何证明呢?
浏览 0
提问于2018-03-02
得票数 1
回答已采纳
1
回答
图灵机不能接受
的
已知
语言
有哪些?
theory
、
turing-machines
、
computability
对于,不接受自己编码
的
图灵机
的
语言
不能被任何图灵机接受。
浏览 36
提问于2012-06-27
得票数 9
回答已采纳
1
回答
一种能被TM识别但不能由TM决定
的
语言
?
computation-theory
、
turing-machines
一种能被TM识别但不能由TM决定
的
语言
可以吗?一种
语言
的
例子,该
语言
可以被商标识别,但不能由商标决定 TM={<M,w> M is a TM that accepts input string w}简而言之,由TM识别的任何字符串都称为TM可识别的,而被TM接受
的
任何字符串则称为TM可
判定
的
。
浏览 2
提问于2016-01-02
得票数 0
回答已采纳
2
回答
所有无限
的
语言
都是不可
判定
的
吗?
turing-machines
、
computation-theory
、
language-theory
我在想,所有无限
的
语言
都是不可决定
的
吗?谢谢你们。
浏览 4
提问于2013-02-13
得票数 0
1
回答
检验一阶逻辑可满足性
的
工具/
语言
?
z3
、
first-order-logic
、
satisfiability
、
sat-solvers
一般来说,一阶逻辑是不可
判定
的
。然而,一阶逻辑
的
一些片段如一元逻辑、BSR片段、分离片段是可
判定
的
. 有一些工具可以作为Z3来解决SAT/SMT问题。是否有检验FOL公式可满足性
的
工具/
语言
?
浏览 13
提问于2019-12-05
得票数 1
回答已采纳
1
回答
上下文无关
语言
的
子集是可决定
的
吗?
formal-languages
L是上下文无关
语言
,J是L
的
子集。J是可
判定
的
吗?上下文无关
的
语言
是可确定
的
。
浏览 13
提问于2020-10-15
得票数 0
1
回答
使用图灵约简证明一种
语言
是不可
判定
的
proof
、
computation-theory
、
turing-machines
、
decidable
我需要证明
语言
L(EVEN) = { M : |L(M)| is even }是不可决定
的
。 我
的
问题是,我无法想出一些以前被证明是无法决定
的
语言
,这些
语言
对展示L <= L(EVEN)是有用
的
。到目前为止,我们在课堂上介绍
的</
浏览 7
提问于2020-02-12
得票数 1
1
回答
总醇下定量
coq
我发现很难完成形式上
的
目标。将此作为一个最小
的
例子:Qed. 由于X有一个有限
的
元
素数
,所以它上有一个有限
的
可
判定
谓词。因此,在这个证明中,我只看了所有这些,并证明了每一个求和
的
正确一面。然而,在更一般
的
情况下,我根本无法移动目标。我
的
直觉是,
浏览 0
提问于2019-11-01
得票数 1
回答已采纳
1
回答
Z3 (和其他求解者)总是在可能
的
情况下使用终止决策过程吗?
arrays
、
z3
、
smt
、
theorem-proving
、
first-order-logic
然而,通过定义一种新
的
带计数器
的
Büchi自动机类,他们按照自动机理论方法建立了这种逻辑
的
可
判定
性。对于我来说,这听起来远不是我所理解
的
SMT求解器作为可
判定
理论与量词
的
决策过程所实现
的
经典量词消除。因此,我
的
问题是:如果一个理论可以像第1篇那样被证明是可
判定
的
,那么Z3 (和其他求解者)是否实现了这些决策过程?换句话说,∀i . 0 ≤ i < n → a[i+1] = a[i]−1查询是用
浏览 8
提问于2022-10-05
得票数 0
回答已采纳
1
回答
图灵机
的
构建决策者而不是决策者
grammar
、
automata
、
turing-machines
、
automata-theory
另外,如何为相同
的
语言
制作decider图灵机图形。
浏览 45
提问于2020-06-28
得票数 1
1
回答
以下
语言
是否可
判定
?L= {<M>:M(x)是一台运行时间为100\x_2+ 200}
的
图灵机。
computation-theory
、
turing-machines
L={:M(x)是一个运行时间为100\x_2+ 200}
的
图灵机。 我觉得我很难判断但我解决不了这个问题。请帮我证明一下。谢谢!
浏览 2
提问于2022-03-28
得票数 0
点击加载更多
扫码
添加站长 进交流群
领取专属
10元无门槛券
手把手带您无忧上云
相关
资讯
C语言/C加加编程学习,素数的求解
每天一道c语言编程题,第四题(c语言经典 求素数)
每日一道c语言编程题,第46题,用筛选法求素数
C+的老豆C语言,C#的林北的C+,C语言的面向过程
C语言编程篇·最简单的C语言程序
热门
标签
更多标签
云服务器
ICP备案
对象存储
实时音视频
即时通信 IM
活动推荐
运营活动
广告
关闭
领券