理解自动机中的识别器和决策器

Question

10

我对机器识别和决定语言的含义感到有些困惑。我觉得我接近了定义，但并不完全正确。

当有人说图灵机 T 识别语言 L 时，意思是

L = { <A> | A is a DFA }

其中DFA表示确定性有限状态自动机

我的理解是，可以构建一个图灵机，对于任何类型的输入（字符串、汽车、人物等），它都能告诉你这个输入是否为DFA。也就是说，它将始终接受DFA并始终拒绝非DFA输入。

也就是说，如果该输入是L的成员。另一个例子是说，某人X是他父亲的识别者，因为无论你放在他面前的是什么东西，他都能告诉你它是否是他的父亲。这个理解正确吗？哪一部分不正确？

另一方面，对于一种语言的判定器(decider)似乎是一种永远不会循环(loops)的图灵机，也就是说，对于任何输入，它始终会在接受或拒绝状态停止。这会与我上面关于识别器的解释类似或相同吗？

谢谢

- devoured elysium

4个回答

2

图灵可判定意味着存在一台图灵机，它接受语言中的所有字符串并拒绝不在语言中的所有字符串。请注意，如果是一个可决定器，该机器不被允许在一个字符串上永远循环，它必须在某个阶段停止并接受或拒绝输入字符串。

图灵可识别意味着存在一台图灵机，它接受该语言中的所有字符串。请注意，该机器不必拒绝不在语言中的字符串，换句话说，该机器被允许在不在语言中的字符串上无限循环。

用高级英语表达，一个决定器机器必须对问题“字符串x是否属于语言A”回答“是”或“否”，而一个识别器必须对同样的问题回答“是”，但如果字符串不属于语言，则可以回答“否”或“无评论，即无限循环”。

- Mohammad Nazayer

2

我认为简单的答案是：

决策者总是停止运行，接受或拒绝

但是

识别器并不总是会停止运行，机器可以接受、拒绝或循环。循环指机器不会停止。

对于识别器，有时我们使用决策者来判断，如果机器处于循环状态，则根据我们的描述，决策者将拒绝。

- Ishwar Pohani

0

我认为，对于图灵机识别像L这样的语言来说，意味着图灵机将会接受与构成L的DFA相同的输入。因此，在这方面上，它们在某种程度上是等效的。

- Bnjmn

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- devoured elysium · Accepted Answer

经过一些学习，我认为我已经理解了这两者之间的区别。

一如既往，问题在于细节。

首先，可判定语言总是可识别语言。

可识别语言是指至少有一台机器的语言是该语言。起初这可能看起来像另一个循环定义，但是...

简单来说，如果你能想到一台机器能够接受它的所有字符串，那么这个语言就是可识别的。

让我们设计一个非常简单的语言：

L = { abc }

这种语言仅由单词 abc 组成。这意味着要证明这种语言是可识别的，必须构建一个能够接受它的机器。我们将非正式地完成它：

当输入为 abc 时，M 是一台接受输入的机器，否则会无限循环。

这个机器接受语言 L 中的所有成员，因此它是 L 的识别器。然而，对于其他所有输入，它将永远挂起。是否存在一台机器，对于每个输入都接受/拒绝，该语言也可以成为可判定语言类的一部分。你能建立一个吗？

（剧透警告!!!11@ # $! 1）

当输入为 abc 时，M' 是一台接受输入的机器，否则拒绝。

也就是说，由于存在一台识别 L 的机器，无论你给它什么输入，它总是能够接受/拒绝，因此该语言被认为是可判定的。

此外，如果您有兴趣某天构建一台识别 L 的机器，您将知道至少有一台机器能够在不陷入在接受 abc 的同时在其他情况下挂起的问题的前提下，始终能够完成该任务！