所有无限的语言都是不确定的吗？

Question

我想知道所有无限的语言都无法决定吗？

它们必须是正确的，因为TM试图决定一种无限的语言会永远循环下去，这使它成为矩形，而不是决定者。

多谢你们。

Answer 1

不，有许多可以决定的无限语言。一个简单的例子是语言{n € N | a^n}，即仅包含字母“ a”的单词的语言。该语言可以与正则表达式匹配a*。所以这是一种普通的语言，因此可以决定。