我在理解机器识别和决定语言的含义时遇到了一些麻烦。我认为我接近定义但不正确。
当有人说图灵机T
识别语言L
时
L = { <A> | A is a DFA }
其中 DFA = 确定性有限自动机
我的理解是,这意味着可以构建一个图灵机,给定任何类型的输入(字符串、汽车、人,等等!)将能够告诉你你作为输入提供的东西是否是 DFA . 我的意思是,将始终接受 DFA 并始终拒绝非 DFA 输入。
也就是说,如果该输入是L
. 另一个例子是说那个人 X 是他父亲的识别者,因为无论你放在他面前的东西是什么,他都能告诉你他面前的东西是否是他的父亲。这个对吗?哪一部分不正确?
另一方面,a decider
over a 语言似乎是一个图灵机,它永远不会loops
,也就是说,对于任何输入,它总是会在接受或拒绝状态下停止。这与我上面关于识别器的解释是否相似或相同?
谢谢