是否正确使用抽水引理？ [英] Am using the pumping lemma correctly?

问题描述

我正试图通过Pumping Lemma证明以下语言不是正常语言。但是我不确定自己是否正确地完成了操作。

I'm trying to prove that the following language is not regular via the Pumping Lemma. But I'm not truly sure if I have done it correctly.

{L = a ^{2 n} | n> = 0}

{L = a²ⁿ | n>= 0 }

到目前为止，我所做的是：

What I've done so far is the following:

s = a < sup> 2 ^p

s = a^2p

x = a ^{2 i}

x = a²ⁱ

y = a ^{2 j}

y = a^2j

z = a ^{2 pij}

z = a^2p-i-j

因此xy ² z = a ^{2 < sup> p + j}

thus xy²z = a^2p+j

这意味着a ^{2 p + j} > a ^{2 p}
，使语言不正常

which means that a^2p+j > a^2p , making the language not regular

我正确吗？还是我出了什么问题？

Am I doing it correctly? or is there something I have wrong?

推荐答案

不太正确，您得出了正确的结论，但推理有些偏离。 Pumping lemma 指出，每种常规语言 L ，存在一个整数 p> = 1 ，其中每个字符串 s 的长度大于或等于 p 可以写为 s = xyz ，其中以下条件成立：

Not quite, you draw the correct conclusion, but the reasoning is a bit off. The Pumping lemma states that for every regular language L, there exists an integer p >= 1 where every string s of length greater than or equal to p can be written as s = xyz where the following conditions hold:

1. y 是非空的


2. xy的长度≤ p


3. xy ⁱ z对于所有i&ge，语言为 L 。 0

1. y is non-empty
2. The length of xy ≤ p
3. xyⁱz is in the language L for all i ≥ 0

您的第一步是正确的，s = a ^{2 p} 为确实比p长。然而，抽水引理指出，满足上述条件，可以将s划分为 s = xyz 。换句话说，存在存在的s的除法为 s = xyz ，但是您不知道选择除法就是什么它应该满足上述三个属性。

Your first step is correct, s = a^2p is indeed longer than p. However, the pumping lemma states that s can be divided as s = xyz satisfying the above conditions. In other words, there exists a division of s as s = xyz, but you don't get to choose what that division is, beyond knowing that it should satisfy the above three properties.

在您的情况下， L 是仅由a组成的语言， a的个数是2的幂。现在取s = a ^{2 p} ，我们知道 L 是（a 2 p ） 2 。从那里开始，如果前两个条件成立，则可以看出，对于 i = 2 ，第三个条件肯定无法成立，因为a 2 p < xy 2 z< （a 2 p ） 2 。 （用简单的英语来说，xy 2 z的长度在2的幂之间，因此它不是 L 的语言， （如果是常规语言）

In your case L is the language consisting of just a's where the number of a's is a power of 2. Now taking s = a^2p, we know that the next longest string in L is (a^2p)². From there, if the first two conditions hold, it can be seen that the third condition certainly cannot hold for i = 2, since a^2p < xy²z < (a^2p)². (In plain english, the length of xy²z is between powers of two, so it is not in the language L as it would have been if it were a regular language)

这篇关于是否正确使用抽水引理？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！