0

Hi, i hope u understand it with this proof:

• Let n be the pumping lemma value and let k be a prime

greater than n.

• If L is regular, the Pumping Lemma implies that a^k can be decomposed into

xyz, |y| > 0, such that xy^iz is in L for all i ≥ 0.

• Assume such a decomposition exists.

• The length of w = xy^k+1z must be a prime if w is in L. But

length(xyk+1z) = length(xyzyk)

= length(xyz) + length(yk)

= k + k(length(y)

= k (1 + length(y))

• The length of xy^k+1z is therefore not prime, since it is the

product of two numbers other than 1. So xy^k+1z is not in L.

• Contradiction!

You

This article has been dead for over six months: Start a new discussion instead