如果M是一个图灵机，我们可以构建一个上下文有关文法G，然后检查上下文敏感的语法是免费的情况下，最后的上下文无关文法是有规律的，或者是它的方式描述。 如果上下文相关的文法G是上下文无关，如果包含在左侧只有非终结符，如果它是有规律的，以及，它包含的非终结符号的产生式规则的结束。
有哪些接受正规语言图灵机，并有其接受不正规语言图灵机。无论是语言是正规与否是语义特性 - 有什么是在语言，而不是与图灵机的形式做的 - 所以，通过赖斯的定理，它不能决定L（M）是否正规。
看到这另一种方法是假设它是可判定，然后推导出矛盾。举例来说，如果这是一个可判定的问题，您可以决定一个任意TM是否接受任何条件;即，L（M）是否是空的语言。要做到这一点，只需用一个新的TM更换halt_accept接受已知的非正规语言构造一个新的TM。这TM的语言，将不规则的 - 所以我们的决胜局将halt_reject - 当且仅当目标TM去到halt_accept一些输入（在这种情况下，它会接受与前缀开头的字符串，并以不规则的语言与任意字串） 。为了使这种结构真正发挥作用，新的TM很可能需要在输入拼音的第一部分和第二部分分离额外的符号;否则，前缀和后缀不规则之间的区别，可以搅浑。
例如：设M是在字母A和M”是其接受回文超过B.然后我们的新TM将超过字母表任何TM输入TM（A联合乙工会{C}），其中c是也不A的元件或B.这个新的TM将具有相同的初始状态为M“并且将使用相同的halt_accept和halt_reject状态为M”。以M其中移动到M的halt_accept状态的任何过渡将代替移动到M”的初始状态和移动磁带头到符号至c的正右侧，而以M其中移动到M中的halt_reject状态的任何过渡反而会移动到halt_reject状态M”。我们的磁带输入到该新TM将看起来像XCY，其中x是在一个字符串，y是一个字符串超过B.假设M接受X。那么M将陆续进入M的halt_accept状态。因此，我们的新TM将进入M”的初始状态，并开始寻找位于y。新TM将接受任何回文Ÿ在B，不规则的语言;和字符串XCY的，其与在B个任何回文结束语言不能是正则语言，除非没有这样的字符串被接受。因为我们知道有过字母表乙回文，语言可能是空的唯一途径是，如果没有串X在造成M至进入halt_accept;即，L（M）必须是空的。因此：
因此，我们可以决定是否M是空的，如果我们能决定的TM是否接受正规语言与否。这是假设你接受“L（M）为空”，是摆在首位不可判定;否则，你能想到的另一个建设为你做的已经知道是不可判定语言的。
这听起来像你问的是这个问题，
Is the following a decidable problem: given a Turing machine M, determine whether L(M) is regular.