1,105,546 Community Members

Star operation and grammer

Member Avatar
Light Poster
30 posts since Apr 2007
Reputation Points: 0 [?]
Q&As Helped to Solve: 0 [?]
Skill Endorsements: 0 [?]

Prove that L = {a^n: n is a prime number} is not regular

I was looking through the solution to it but dont understand it at all, could anyone help explain how to solve it?


Member Avatar
Newbie Poster
23 posts since Apr 2010
Reputation Points: 0 [?]
Q&As Helped to Solve: 2 [?]
Skill Endorsements: 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!

This article has been dead for over three months: Start a new discussion instead
Start New Discussion
View similar articles that have also been tagged: