# Prove language is regular [duplicate]

let's have these two languages in the alphabet $\{a,b,c\}$:

$L_1 = \{ w \mid w \text{ is a palindrome and$|w| < 200$}\}$

$L_2 = \{ w \mid w \text{ is a suffix of$u$and$|u|$is a prime number and$u$doesn't contain a$c$}\}$

and I have to prove that $L_1 ∪ L_2$ is regular.

So my idea is I have to prove both languages are regular and therefore their union would be regular. $L_1$ is obviously regular since it's finite. I also know that the language consisting of all suffixes of words from a regular language is also regular, so I narrowed it down to proving that

$L = \{w \mid |w| \text{ is a prime number and$w$doesn't contain a$c$}\}$

any ideas on that one? Thanks in advance.

• Your language $L$ isn't regular: as I recall, it's not easy but you can show this using the pumping lemma. Hint: rewrite the definition of $L_2$ in simpler terms. What does it mean to be a suffix of some $c$-free string whose length is prime? – David Richerby Jul 5 '15 at 20:28
• I do not see why this is a duplicate. The main argument of the proof is that there are infinitely many primes. None of the algorithms described in the reference question is used to prove that $L_2 = \{a,b\}^*$. This is rather a combinatorial question. – J.-E. Pin Jul 6 '15 at 13:21

The language $L$ is not regular, but $L_2$ is. In fact $L_2 = \{a,b\}^*$. Indeed if $w \in L_2$, then by definition, $w$ is suffix of a word of $\{a,b\}^*$ and thus $w \in \{a,b\}^*$. Thus $L_2 \subseteq \{a,b\}^*$. To prove the opposite inclusion, consider a word $w \in \{a,b\}^*$. Let $p$ be a prime such that $p \geqslant |w|$ and let $u = a^{p-|w|}w$. By construction, $|u| = p$, $u \in \{a,b\}^*$ and $w$ is a suffix of $u$, and thus $w \in L_2$.