Member Avatar for philmetz

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?

Thanks

  • 2 Contributors
  • 1 Reply
  • 117 Views
  • 10 Hours Discussion Span
  • Latest Post Latest Post by agugglez
Member Avatar for agugglez

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!

Be a part of the DaniWeb community

We're a friendly, industry-focused community of developers, IT pros, digital marketers, and technology enthusiasts meeting, networking, learning, and sharing knowledge.