为什么a^nb^n n>=0不是常规的?

你要找的是 Pumping lemma for regular languages .

这里是一个 example 关于你的确切问题:

实例:
设L={A ^米 乙 ^米 m=1×}。
那我就不正常了。
证明:假设n在抽运引理中。
让W= A ⁿ 乙 ⁿ .
设w=xyz为抽运引理。
因此,XY ^二 但是,xy ^二 Z比B__浼浼浼浼浼浼浼浼浼

因为您不能编写一个有限状态机来计算“a”和“b”符号的相同序列。简而言之,FSMS不能“计数”。想象一下这样一个FSM:你会给符号“A”多少个州?多少到“B”?如果你的输入序列有更多呢?

请注意,如果n<=x和x是一个整数值,您可以准备这样的fsm(通过有一个具有许多状态,但仍然是一个有限的数字);这样的语言将是规则的。

有限状态自动机和下推自动机一样,没有数据结构(堆栈)内存。是的,它可以给你一些“A”和一些“B”,但不是确切的“A”和“B”。