Skip to main content
1 of 2
lox
  • 1.7k
  • 1
  • 10
  • 16

We use the pumping lemma for regular languages.

$w \in L$, $|w| = n$, and $n$ is prime.

according to the lemma, $w$ can distribute to $xyz$ s.t:

$\bullet y \neq \epsilon $

$\bullet |xy| < n$

$\bullet$ for any $i \geq 0$ $ xy^iz \in L$

Now, let us denote $|y| = k$. we know that $k \geq 1$ by the lemma, and we also know that $k$ must be an even number. Why? if it was odd, then by pumping it once $|xyyz|$ would be $n+k$, and since $n$ is odd the sum of two odds is even $\rightarrow$ contradiction.

Now we only need to think of an $i$, where $|xy^iz|$ is not prime.

let's choose $ i = \frac {2n}{k}$. It's definitely an integer, since k is even and $n \geq k$.

$|xy^{i+1}z| = n+ik = n+\frac{2n}{k} k= 3n$

since $3n$ is not prime, we reached a contradiction and we can conclude $L$ is not regular.

lox
  • 1.7k
  • 1
  • 10
  • 16