如何证明 {(a^m)(b^n)(c^k): m!=k 且 m,n,k ∈ N} 是非常规的？

Question

这是CS课程“计算理论”中的一个问题，关于常规或非常规语言的证明。

如何证明 {(a^m)(b^n)(c^k): m!=k 且 m,n,k ∈ N} 是非常规的？

我尝试通过泵浦定理来解决它，但没有成功。

Answer 1

假设您有机器。有两个前缀

a^i

和

a^j

，i≠j，它们必须都进入相同的状态，因为您只有有限数量的状态。但是你的机器无法区分

a^ibc^i

和

a^jbc^i

之间的区别，其中一个应该通过，另一个不应该通过。