0
$\begingroup$

This question already has an answer here:

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?

$\endgroup$

marked as duplicate by Apass.Jack, David Richerby, D.W. Mar 28 at 19:35

This question has been asked before and already has an answer. If those answers do not fully address your question, please ask a new question.

1
$\begingroup$

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.

$\endgroup$

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