如果 M 是图灵机，那么问题是 L(M) = A Regular Language, Decidable？
If M is a turing machine, the question if L(M) = A Regular Language, Decidable?
如果M是图灵机，我们可以构造一个上下文敏感文法G，然后检查上下文敏感文法是否是上下文无关的，最后以描述的方式判断上下文无关文法是否是正则的。
如果 A 上下文相关文法 G 是上下文无关的，如果仅在左侧包含非终结符，并且如果它也是规则的，则它在产生式规则的末尾包含非终结符。
听起来你问的问题是，
Is the following a decidable problem: given a Turing machine M, determine whether L(M) is regular.
答案似乎是否定的：https://cs.stackexchange.com/a/85237
有接受常规语言的图灵机，也有接受不规则语言的图灵机。一种语言是否规则是一种语义 属性 - 与语言中的内容有关，与图灵机的形式无关 - 因此，根据莱斯定理，无法确定 L(M) 是否是常规的。
另一种看待这个问题的方法是假设它是可判定的，然后得出一个矛盾。例如，如果这是一个可判定的问题，您可以决定任意 TM 是否接受任何字符串；即 L(M) 是否为空语言。为此，只需将 halt_accept 替换为接受已知非常规语言的新 TM，即可构造一个新 TM。该 TM 的语言将是不规则的 - 因此我们的决策者将 halt_reject - 当且仅当目标 TM 在某些输入上达到 halt_accept 时（在这种情况下，它将接受以该前缀开头并以该前缀结尾的字符串任何不规则语言的字符串）。为了使这种结构真正起作用，新的 TM 可能需要在输入字母表中有一个额外的符号来分隔第一部分和第二部分；否则会混淆前缀和不规则后缀的区别。
示例：假设 M 是字母 A 上的输入 TM，M' 是接受 B 上回文的任何 TM。那么我们的新 TM 将是字母表上的（A union B union {c}），其中 c 不是A 或 B 的一个元素。此新 TM 将具有与 M' 相同的初始状态，并将使用与 M' 相同的 halt_accept 和 halt_reject 状态。 M 中移动到 M 的 halt_accept 状态的任何转换将改为移动到 M' 的初始状态并将磁带头移动到紧靠 c 右侧的符号，而 M 中移动到 halt_accept 状态的任何转换M 中的 halt_reject 状态将转为 M' 中的 halt_reject 状态。我们对这个新 TM 的磁带输入看起来像 xcy，其中 x 是 A 上的字符串，y 是 B 上的字符串。假设 M 接受 x。然后 M 将进入 M 的 halt_accept 状态。因此，我们的新 TM 将进入 M' 的初始状态并开始查看 y。新的 TM 会接受 B 上的任何回文 y，这是一种不规则语言；并且以 B 上的任何回文结尾的字符串 xcy 的语言不能是常规语言，除非不接受这样的字符串。因为我们知道字母 B 上有回文，所以语言可能为空的唯一方法是 A 上没有字符串 x 导致 M 输入 halt_accept；也就是说，L(M) 必须为空。因此：
- 如果我们的新 TM 被确定为常规的，我们就知道 M 是空的
- 如果我们的新 TM 被确定为不规则的，我们知道 M 是非空的
因此，如果我们可以决定 TM 是否接受正则语言，我们就可以决定 M 是否为空。这假设您首先接受 "L(M) is empty" 是不可判定的；否则，你可能会想到另一种你已经知道的语言的结构是不可判定的。
如果M是图灵机，我们可以构造一个上下文敏感文法G，然后检查上下文敏感文法是否是上下文无关的，最后以描述的方式判断上下文无关文法是否是正则的。
如果 A 上下文相关文法 G 是上下文无关的，如果仅在左侧包含非终结符，并且如果它也是规则的，则它在产生式规则的末尾包含非终结符。
听起来你问的问题是，
Is the following a decidable problem: given a Turing machine M, determine whether L(M) is regular.
答案似乎是否定的：https://cs.stackexchange.com/a/85237
有接受常规语言的图灵机，也有接受不规则语言的图灵机。一种语言是否规则是一种语义 属性 - 与语言中的内容有关，与图灵机的形式无关 - 因此，根据莱斯定理，无法确定 L(M) 是否是常规的。
另一种看待这个问题的方法是假设它是可判定的，然后得出一个矛盾。例如，如果这是一个可判定的问题，您可以决定任意 TM 是否接受任何字符串；即 L(M) 是否为空语言。为此，只需将 halt_accept 替换为接受已知非常规语言的新 TM，即可构造一个新 TM。该 TM 的语言将是不规则的 - 因此我们的决策者将 halt_reject - 当且仅当目标 TM 在某些输入上达到 halt_accept 时（在这种情况下，它将接受以该前缀开头并以该前缀结尾的字符串任何不规则语言的字符串）。为了使这种结构真正起作用，新的 TM 可能需要在输入字母表中有一个额外的符号来分隔第一部分和第二部分；否则会混淆前缀和不规则后缀的区别。
示例：假设 M 是字母 A 上的输入 TM，M' 是接受 B 上回文的任何 TM。那么我们的新 TM 将是字母表上的（A union B union {c}），其中 c 不是A 或 B 的一个元素。此新 TM 将具有与 M' 相同的初始状态，并将使用与 M' 相同的 halt_accept 和 halt_reject 状态。 M 中移动到 M 的 halt_accept 状态的任何转换将改为移动到 M' 的初始状态并将磁带头移动到紧靠 c 右侧的符号，而 M 中移动到 halt_accept 状态的任何转换M 中的 halt_reject 状态将转为 M' 中的 halt_reject 状态。我们对这个新 TM 的磁带输入看起来像 xcy，其中 x 是 A 上的字符串，y 是 B 上的字符串。假设 M 接受 x。然后 M 将进入 M 的 halt_accept 状态。因此，我们的新 TM 将进入 M' 的初始状态并开始查看 y。新的 TM 会接受 B 上的任何回文 y，这是一种不规则语言；并且以 B 上的任何回文结尾的字符串 xcy 的语言不能是常规语言，除非不接受这样的字符串。因为我们知道字母 B 上有回文，所以语言可能为空的唯一方法是 A 上没有字符串 x 导致 M 输入 halt_accept；也就是说，L(M) 必须为空。因此：
- 如果我们的新 TM 被确定为常规的，我们就知道 M 是空的
- 如果我们的新 TM 被确定为不规则的，我们知道 M 是非空的
因此，如果我们可以决定 TM 是否接受正则语言，我们就可以决定 M 是否为空。这假设您首先接受 "L(M) is empty" 是不可判定的；否则，你可能会想到另一种你已经知道的语言的结构是不可判定的。