为什么{a^nb^n | n>=1} 不是正则语言？

Question

我正在关注 this 视频，想知道为什么 {aⁿbⁿ | n≥1}不是正则语言？

Answer 1

有穷自动机必须识别正则语言。由于 n 不受任何常数的限制，因此自动机不能是有限的。

Answer 2

如果将“正规语言”定义为“有限自动机识别”，设m为这种自动机的状态数。如果自动机要识别a¹b¹,a²b² , …, a^m+1b^m+1,自动机读取后状态不能相同a¹, a², …, a^m+1, 矛盾.