prove that language is not regular (prime numbers)

Question

$$\sum_{p\,\in\,\text{Prime}}(cb^*)^p + (b+c)^*cc(b+c)^*$$ Show that language is not regular.

We see that there are two possibilities: $p$ (prime) blocks of $b's$ separated by $c$ or any string of $b$ and $c$ containg substring $cc$

I have no idea how to solve it. Help me, please.

Answer 1

Hint you can use the pumping lemma for regular languages:

• Assume the existence of an automaton with $m$ states which recognizes your language
• Take a very large $p>m$ and the word $w=(cb)^p$
• Apply the lemma there exist $r,s,t$ such that $rst=(cb)^p$ and we have three cases $s=(cb)^k$ or $s=b(cb)^k$ or $(cb)^kc$
• conclude that either $(cb)^{p+nk}$ or $(cb)^{t}(c(cb)^k)^n(cb)^{p-k-t}$ or $\cdots$ are elements of $L$
• conclude by a contradiction in each case

Answer 2

Instead of the pumping lemma, you can use the Myhill-Nerode theorem by showing that if $d\ge 1$, the strings $(cb)^m$ and $(cb)^{m+d}$ have a distinguishing extension. The following lemma is helpful.

Lemma. Let $d$ be any positive integer. For each $m\in\Bbb Z^+$ there is a prime $p\ge m$, such that $p+d$ is composite.

HINT for proving the lemma: if it were false, there would be an $m\in\Bbb Z^+$ such that $p+d$ was prime for each prime $p\ge m$.

Answer 3

I try to use Hint Let $w=(cb)^p=rst$
I consider we have four cases, not three:
1) $(cb)^k$
2) $b(cb)^k $
3) $(cb)^kc $
4) $(bc)^k $

Let's use lemma:
For every $n$ either $(cb)^{p+nk}$ or $(cb)^tc(b(cb)^k)^{n}(cb)^{p-k-t} $ or $(cb)^t((cb)^kc)^nb(cb)^{p-t-k} $ or $(cb)^tc(bc)^{kn}b(cb)^{p-k-t} \in L$
Conclude by contradiction for every case:
1)$(cb)^{p+nk}$ - when $n=p$ we have $(cb)^{p(1+k)}$. It isn't prime number.
2)$(cb)^tc(b(cb)^k)^{n}(cb)^{p-k-t} \notin (b +c)^*cc(b+c)^*$
3)$(cb)^t((cb)^kc)^nb(cb)^{p-t-k} \in (b +c)^*cc(b+c)^*$
4)$(cb)^tc(bc)^{kn}b(cb)^{p-k-t}$: $p-k-t+kn+t+1=p-k+kn+1$ exists $n$ such that $p-k+kn+1$ is not prime.

As you know there is problem in 3). What about it ? What should I do ?

Answer 4

You could use the fact that regular languages are closed under intersection and inverses of homomorphisms.

Let $L$ be your language. If it were regular, then $K = L \cap (cb)^*$ would also be regular. Let $f: a^* \to (b+c)^*$ be the homomorphism defined by $f(a) = bc$. Then $f^{-1}(K)$ would also be regular. Now we have $$ K = L \cap (cb)^* = \sum_{p\,\in\,\text{Prime}}(cb)^p \quad \text{and} \quad f^{-1}(K) = \sum_{p\,\in\,\text{Prime}}a^p $$ Thus if $L$ were regular, then $\{ a^p \mid p \text{ is prime}\}$ would be a regular subset of $a^*$. Can you conclude now?