dev*_*ium 9 computer-science computation-theory
我在掌握机器识别和决定语言意味着什么方面遇到了一些麻烦.我认为我接近定义但不对.
当有人说图灵机T识别语言L在哪里时
L = { <A> | A is a DFA }
其中DFA =确定性有限自动机
我的理解是,它意味着可以构建一个图灵机,给出任何类型的输入(字符串,汽车,人,等等!)将能够告诉你,你给它作为输入的东西是否是DFA .我的意思是,我将始终接受DFA,并始终拒绝非DFA输入.
也就是说,如果该输入是其成员L.另一个例子就是说X家是他父亲的认可者,无论你摆在他面前的是什么,他都能告诉你他面前的是他父亲是不是他的父亲.它是否正确？哪部分不正确？
另一方面,一种decider语言似乎永远不会是图灵机loops,也就是说,对于任何输入,它总是会在接受或拒绝状态下停止.这与我上面关于识别器的解释是不是相似或相同？
谢谢
dev*_*ium 12
经过一番研究,我认为我得到了两者之间的区别.
首先,可判定语言始终是一种可识别的语言.
可识别的语言是至少有一台机器以其语言为语言的语言.起初,这可能看起来像是那些循环定义中的一个,但是......
用非专业术语来说,如果你能想到一台能够接受其所有字符串的机器,那么语言就是可识别的.
让我们设计一些非常简单的语言:
L = { abc }
这种语言只由abc这个词组成.这意味着要证明这种语言是可识别的,必须构建一台接受它的机器.我们非正式地做:
M是当输入接受abc时的机器,否则无限循环.
这台机器接受语言L的所有成员,因此它是L的识别器.但是,对于所有其他输入,它将永远挂起.如果机器存在,对于每个输入接受/拒绝,该语言也可以是可判定语言类的一部分.你能建一个吗？
(剧透警报!!! 11 @#$!1)
M'是指当abc作为输入接受时的机器,否则拒绝.
也就是说,因为有一台识别L的机器,无论你给它什么输入,总是接受/拒绝,语言被认为是可判定的.
此外,你是否有兴趣建立一台识别L的机器,你知道你至少有一台机器能够始终如一地完成它而不会产生能够接受abc但在其他情况下失败的问题,永远挂在上面!