我想知道所有无限语言都无法确定吗？
他们一定是对的，因为试图决定一种无限语言的 TM 只会永远循环，这使它成为一个recgonizer，而不是一个决定者。
多谢你们。
问问题
7683 次
2 回答
6
不，有许多无限的语言是可判定的。一个简单的例子是语言{n € N | a^n}，即只包含字母“a”的单词的语言。这种语言可以通过正则表达式匹配a*。所以它是一种常规语言，因此是可判定的。
于 2013-02-13T15:49:26.663 回答
2
正如 sepp2k 指出的那样，a*它是一种常规语言，因此是可判定的。
所有有限语言都是正则的。一些无限的语言是有规律的。只有无限的语言是不可判定的。
要不可判定，语言中必须存在导致 TM 失败的单独字符串。实际上，这样的字符串肯定有无限多（否则，表现不佳的字符串可以由特殊情况逻辑处理）。
因此，对于不可判定性来说，语言是无限的是必要的，但不是充分的。
于 2013-02-13T16:47:55.620 回答