computer-science - 为什么是 {a^nb^n | n >= 0} 不规则？

Question

在我参加的 CS 类(class)中，有一个不规则语言的例子:

{a^nb^n | n >= 0}

我可以理解它是不规则的，因为没有有限状态自动机/机器可以编写来验证和接受此输入，因为它缺少内存组件。 (如果我错了，请纠正我)

wikipedia entry on Regular Language也列出了这个例子，但没有提供一个(数学)证明为什么它不规则。

任何人都可以启发我并为此提供证据，或者指出我也是一个很好的资源？

Answer 1

您要找的是Pumping lemma for regular languages .

这是一个 example与您的确切问题:

Examples:
Let L = {a^mb^m | m ≥ 1}.
Then L is not regular.
Proof: Let n be as in Pumping Lemma.
Let w = aⁿbⁿ.
Let w = xyz be as in Pumping Lemma.
Thus, xy²z ∈ L, however, xy²z contains more a’s than b’s.