L= {a^n ^m\ n>m}是常规语言还是不规则语言？

Question

我在解决/证明这个问题上遇到了麻烦。有什么想法吗？

Answer 1

语言是固定的。在Grijesh Chauhan的回答中，他的错误是，在第二步中，他选择了一个b^m > a^n的字符串，这很好，但是当我们抽水时，我们得到了一个字符串，它不遵循这个规则，但仍然在语言中。例如，选择a^P和b^(P+3)，其中P= 3，我们得到aaabbbbbb。如果我们做x(y^i)z证明，我们得到x= aa，y=a，z= bbbbbb。现在我可以是任何数字，比方说10。字符串现在是aaaaaaaaaaaabbbbbb。这个字符串不遵循我们设置的规则(b^m > a^n)，但它仍然在语言中。所以我们不能证明字符串是非正则的。

另外，我们可以从这个表达式创建一个NFA，所以它必须是常规的NFA。