Prove that the following language L over alphabet $\{1\}$ is not regular. $L = \{w \mid |w| = k, \text{ where } k \text{ is a prime number}\}$

Suppose the language is regular for contradiction. Since $L$ is regular, we apply the pumping lemma. Let $p$ be given by PL such that the decomposition of the string $w = xyz$:

  1. for each $i \geq 0$, $xy^iz \in L$;

  2. $|y| > 0$;

  3. $|xy| \leq p$.

There are infinitely prime numbers, then there exists a string $w \in L$, such that $|w| = k$ is the first prime number $> p$. Hence $w \in L$ and $|w| > p$ and we can decompose $w = xyz$ in order to satisfy the above conditions. Consider $v = xy^{k+1}z$, by 1) above $|v|$ must be a prime. But $|v| = k(1+|y|)$. But $k$ divides $k(1 + |y|)$ and $k > 1$. Hence $|v|$ is not a prime. We reach a contradiction. $L$ is not regular.

How can I use 2) and 3) conditions?

  • $\begingroup$ Haven't you implicitly used those conditions when you said "Hence w∈L and |w|>p and we can decompose w=xyz in order to satisfy the above conditions."? $\endgroup$ – John Douma Mar 19 '18 at 13:33
  • $\begingroup$ Yes, but I was wondering whether I am obliged to use them explicitly ? $\endgroup$ – Hello Mar 19 '18 at 13:38
  • $\begingroup$ If you were trying to use the pumping lemma to prove that the language was regular you would have to be explicit in your construction of $y$ because you would have to show that $xy^nz\in L$. In your case you don't care what $y$ is. You assume $L$ is regular so you are guaranteed such a decomposition as long as the prime is large enough. $\endgroup$ – John Douma Mar 19 '18 at 13:43

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.