Si consideri il linguaggio
$$ L_{pr}=\{w \in \{1\}^* \ | \ |w| \text{ è un numero primo } \} = \{1^p \ | \ p \text{ è un numero primo }\} $$
cioè il linguaggio dei numeri primi in rappresentazione unaria. Esso non è regolare; per dimostrarlo, si applicano il pumping lemma e alcune proprietà dei numeri primi.
Innanzitutto, si suppone per assurdo che $L_{pr}$ sia regolare, e che $N$ sia la sua costante di pumping. Siccome i primi sono infiniti, si può sicuramente scegliere un numero primo $p \geq N+2$, che corrisponde alla stringa $w = 1^p \in L_{pr}$. Per definizione, $|w| = p> N$, dunque secondo il pumping lemma deve esistere una scomposizione $w = xyz$ che verifichi le tre proprietà del lemma:
Assumendo le proprietà 1 e 2, si dimostra che la 3 non può essere verificata.
Prima di procedere con la dimostrazione, bisogna studiare alcuni fatti relativi alla lunghezza delle stringhe in cui è scomposta $w$. La lunghezza di $y$ deve essere $|y|\geq 1$ per la 1, e $|y|\leq |xy| \leq N$ per la 2, quindi complessivamente si ha $|y|=m$ con $1\leq m \leq N$. Invece, la lunghezza delle altre parti della stringa è ottenuta semplicemente sottraendo la lunghezza di $y$ da quella totale:
$$ |xz| = |xyz| - |y| = |w| - |y| = p-m $$
Sapendo che $p\geq N+2$ (per definizione) e $N\geq m$, si ricava che
$$ p \geq N + 2 \geq m + 2 $$
ovvero che
$$ p-m \geq 2 $$
Tornando al pumping lemma, secondo la proprietà 3 con $k = p-m$ la stringa $xy^{p-m}z$ dovrebbe appartenere a $L_{pr}$. Tuttavia, la sua lunghezza è
cioè un numero avente due fattori. Per definizione, questo potrebbe essere un numero primo solo se uno dei due fattori fosse uguale a 1, ma invece essi sono entrambi maggiori di 1, in base ad alcuni dei fatti visti prima:
$$ p-m \ge2 > 1 \\ m\geq 1 \rarr m+1 \geq 1+1> 1 $$
Segue che $xy^{p-m}z \not \in L_{pr}$, contrariamente a quanto affermato dal pumping lemma. Essendo giunti a un assurdo, si deduce che l’ipotesi che $L_{pr}$ fosse regolare è scorretta, dimostrando così che esso non è un linguaggio regolare.