Show, that $L$ is not regular but satisfies the pumping-property.

Question

Show, that $L_{1}:=L\left((a \cup b)^{*} \cdot(a a \cup b b) \cdot(a \cup b)^{*}\right) \cup\left\{w \in\{a, b\}^{*}\mid \lvert w \rvert \text { is prime number}\right\}$ is not regular but satisfies the pumping-property/lemma of regular languages.

Let $n=3$ be the pumping-length of $w$. Now we consider an arbitrary word $w=w_1w_2\dots w_{\lvert w\rvert}\in L$ with $\lvert w\rvert \geq3$.

• Case 1: $aa$ is a substring of $w$
  • Case 1a: $w$ begins with $aa$
    We can chose $x=aa$, $y=w_3$ and $z=w_4\dots w_{\lvert w\rvert}$ and we can pump up $y$.
  • Case 1b: $w$ does not begin with $aa$
    We can chose $x=\lambda$, $y=w_1$ and $z=w_2\dots w_{\lvert w\rvert}$, $aa\in z$ and we can pump up $y$.
• Case 2: $bb$ is a substring of $w$
  This case is analogue to Case 1
• Case 3: Not Case 1 and not Case 2, which means, that $w$ does not contain $aa$ or $bb$ and the length of $w$ must be a prime number. In other words, every $a$ gets followed by $b$ and vice versa.
  • Case 3a: $w$ begins with $a$
    Now my problem is, that I don't know how to choose $x,y,z\in\Sigma^*$ in order to satisfy Case 3a. I even doubt, that this language satisfies the pumping-property anyway, but since the question is to prove that it indeed has the pumping property, I'm not really sure how to go on now. I would appreciate some hints and corrections if possible.
  • Case 3b: $w$ does not begin with $a$
    See above.

Answer 1

Hint. Let $A = \{a,b\}$. Note that the complement of the language $A^*(aa + bb)A^*$ is the set of words containing neither two consecutive $a$'s, nor two consecutive $b$'s, that is $$(1+b)(ab)^*(1+a).$$ It follows that your language is equal to $L_1 + L_2$ where $$ L_1 = A^*(aa + bb)A^* \quad \text{and} \quad L_2 = \{u \in (1+b)(ab)^*(1+a) \mid |u| \text{ is prime }\} $$ You have already seen that you can pump a word of $L_1$ and stay in $L_1$. For a word in $L_2$, you can take a factorisation $w = xyz$ where $y = a$ or $y = b$. When you pump $y$, you obtain at least two consecutive $a$'s or $b$'s. In other words, you are back in $L_1$ and hence in $L$.