我在理解机器识别和决定语言的含义时遇到了一些麻烦。我认为我接近定义但不正确。
当有人说图灵机T识别语言L时
L = { <A> | A is a DFA }
其中 DFA = 确定性有限自动机
我的理解是，这意味着可以构建一个图灵机，给定任何类型的输入（字符串、汽车、人，等等！）将能够告诉你你作为输入提供的东西是否是 DFA . 我的意思是，将始终接受 DFA 并始终拒绝非 DFA 输入。
也就是说，如果该输入是L. 另一个例子是说那个人 X 是他父亲的识别者，因为无论你放在他面前的东西是什么，他都能告诉你他面前的东西是否是他的父亲。这个对吗？哪一部分不正确？
另一方面，a deciderover a 语言似乎是一个图灵机，它永远不会loops，也就是说，对于任何输入，它总是会在接受或拒绝状态下停止。这与我上面关于识别器的解释是否相似或相同？
谢谢
经过一番研究，我想我得到了两者之间的区别。
首先，可判定的语言始终是可识别的语言。
可识别的语言是至少有一台机器将其作为其语言的语言。起初，这可能看起来像是这些循环定义中的一个，但是..
通俗地说，如果您能想到一台能够接受其所有字符串的机器，则可以识别一种语言。
让我们设计一些非常简单的语言：
L = { abc }
这种语言仅由单词 abc 组成。这意味着要证明这种语言是可识别的，必须建造一台接受它的机器。我们将非正式地这样做：
M 是当给定 abc 作为输入时接受的机器，否则无限循环。
这台机器接受语言 L 的所有成员，因此它是 L 的识别器。然而，对于所有其他输入，它将永远挂起。是否存在对于每个输入都接受/拒绝的机器，这种语言也可以是可判定语言类的一部分。你能建一个吗？
（剧透警告！！！11@#$!1）
M' 是当将 abc 作为输入时接受，否则拒绝的机器。
也就是说，由于有一台机器可以识别 L 并且无论您提供什么输入，它总是会接受/拒绝，因此该语言被认为是可判定的。
此外，如果你有兴趣在某一天建造一台识别 L 的机器，你会知道你至少有一台机器能够始终做到这一点，而不会出现能够接受 abc 但在其他情况下惨遭失败的问题，永远挂着！
我认为的简单答案是：
决策者总是停止，接受或拒绝
但
识别器并不总是停止，机器可以接受、拒绝或循环。通过循环意味着机器不会停止。
对于识别器，有时我们使用决策器来决定，如果机器处于循环中，那么决策器将根据我们的描述拒绝。
图灵可判定意味着有一个图灵机接受该语言中的所有字符串并拒绝所有不是该语言的字符串，请注意，如果该机器是判定器，则不允许该机器永远循环在一个字符串上，它必须在一个阶段停止并接受或拒绝输入字符串。
图灵可识别意味着有一个图灵机可以接受该语言的所有字符串。请注意，机器不必拒绝不属于该语言的字符串，换句话说，允许该机器在不属于该语言的字符串上永远循环。
用高级英语来说，决策机器必须对问题“是语言 A 中的字符串 x”回答“是”或“否”如果字符串在语言但如果字符串不是，则允许说“否”或“无评论，即永远循环”
我认为图灵机识别诸如 L 这样的语言意味着图灵机将接受与组成 L 的 DFA 相同的所有输入。因此，它们在某种意义上是等价的。