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

How should one go about proving this? Should I use pumping lemma for this?


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$.

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

let's choose $ i = n$.

$|xy^{i+1}z| = n+ik = n+kn= (k+1)n$

since $(k+1)n$ is not prime (divides by $k+1$), we reached a contradiction and we can conclude $L$ is not regular.

| cite | improve this answer | |

Not the answer you're looking for? Browse other questions tagged or ask your own question.