PadhaikoAll subjects

Past exam question: 2082 Chaitra (Regular), Q6

Theory of Computation · 3 marks

Open in the Padhaiko app

Topic: Closure Properties, Pumping Lemma & Decision Algorithms

Question

Using 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:

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.

Answer:

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.

All past exam questions for Theory of Computation