0
$\begingroup$

This question already has an answer here:

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.

$\endgroup$

marked as duplicate by David Richerby, D.W., Luke Mathieson, Juho, Raphael Jul 6 '15 at 9:18

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$ 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? $\endgroup$ – David Richerby Jul 5 '15 at 20:28
  • $\begingroup$ 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. $\endgroup$ – J.-E. Pin Jul 6 '15 at 13:21
1
$\begingroup$

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$.

$\endgroup$
  • $\begingroup$ Wow thanks, never thought of it that way :) $\endgroup$ – Robert Jul 6 '15 at 7:53

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