为什么{a ^ nb ^ n | n> = 0}是否不规则？ [英] Why is {a^nb^n | n >= 0} not regular?

问题描述

在CS课程中，我以一个非常规语言的示例为例：

In a CS course I'm taking there is an example of a language that is not regular:

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

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

I can understand that it is not regular since no Finite State Automaton/Machine can be written that validates and accepts this input since it lacks a memory component. (Please correct me if I'm wrong)

有关常规语言的维基百科条目也列出了此示例，但没有提供（数学上的）证明其不规则的原因。

The wikipedia entry on Regular Language also lists this example, but does not provide a (mathematical) proof why it is not regular.

有人可以启发我吗？

Can anyone enlighten me on this and provide proof for this, or point me too a good resource?

推荐答案

您正在寻找的是常规语言的抽取引理。

这里是一个示例，其中包含您的确切问题：

Here is an example with your exact problem:

示例：

令L = {a ^m b ^m | m≥1}。

那么L不是正规的。

证明：让n等于抽水引理。

令w = a ⁿ b ⁿ 。

令w = xyz像抽水引理中一样。

因此，xy ² z ∈L，但是xy ² z包含的a大于b。

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.

这篇关于为什么{a ^ nb ^ n | n> = 0}是否不规则？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！