Past exam question: 2082 Chaitra (Regular), Q6
Open in the Padhaiko appUsing pumping lemma show that the language : where is a prime number is not regular.
Solution
Pumping Lemma Statement and Proof Strategy: The Pumping Lemma for regular languages states that if is regular, there exists a pumping length such that any string with can be written as satisfying:
We prove by contradiction. Assume that is regular. Let be its pumping length.
Selection of String and Adversarial Decomposition: Choose a prime number such that (since infinitely many primes exist, such a always exists). Consider the string:
Since , the pumping lemma guarantees a decomposition such that:
Because the alphabet contains only symbol , we have , , and , where with and .
Pumping to Produce a Composite Length: According to condition (3), must belong to for all integers .
The length of the pumped string is:
For :
Notice that:
- (since is prime),
- (since ).
Consequently, is the product of two integers strictly greater than , which means is composite (not a prime number).
Therefore, , which directly contradicts the pumping lemma. Hence, our assumption was false, and is not regular.
By assuming is regular with pumping length , selecting for prime , and pumping with , the length becomes . Because and , this length is composite, contradicting the pumping lemma. Thus, is not regular.