在我接受的CS课程中，有一个不常规的语言示例：
{a^nb^n | n >= 0}
我可以理解它不常规，因为没有有限状态自动机/机器可以编写验证和接受此输入，因为它缺少一个内存组件。 （如果我错了，请纠正我）
wikipedia entry on Regular Language也列出了这个例子，但没有提供（数学）证明为什么它不规则。
任何人都可以启发我并为此提供证据，或者指出我太好的资源？
你要找的是Pumping lemma for regular languages。
这是一个example与你的确切问题：
例子： 设L = {ambm | m≥1}。 然后L不规律。 证明：让我像泵浦引理一样。 让w = anbn。 设w = xyz与泵浦引理相同。 因此，xy2z∈L，然而，xy2z包含的a比b更多。
因为你不能编写一个有限状态机来“计算”'a'和'b'符号的相同序列。简而言之，FSM无法“计算”。尝试想象这样一个FSM：你会给符号'a'多少个州？ 'b'有多少？如果输入序列有更多，该怎么办？
请注意，如果n <= X且X为整数值，则可以准备这样的FSM（通过使其具有大量状态，但仍然是有限数）;这种语言会定期。
有限状态自动机没有数据结构（堆栈） - 内存与下推自动机一样。是的它可以给你一些'a's后跟一些'b'但不是'a'的确切数量，其次是'b'。