Regular language union non-regular language

Question

I have the following languages:

$ L_1 = (P \cup \{b\})^*$

$P = \{a^p | p = prime\}$ for example $ \{aa, aaa, aaaaa\} $

I am told that $L_1$ is regular and thus I should be able to create a finite automata for it, correct? But since $P$ cannot possibly be regular how can I draw this $union$ ?

This is what I have so far: The $\{b\}$ part is fairly straight forward, but I am stuck on how to represent $P$

For example a valid string could be $\epsilon$, $bb$ or $aab$ but since I cannot keep track on how many a's we have gone trough so far how could I possible make a finite automata out of it? or would $aab$ be a invalid string and the regular expression of the whole thing would simply be $b^*$?

Answer 1

Given

$$L = (P \cup \{b\})^*, \quad P = \{a^p \mid p \text{ is prime}\}$$

you want to show that $L$ is regular.

Hint:

• Set $P' = \{aa, aaa\} \subseteq P$ and observe that $L' = \big(\{aa, aaa, b\}\big)^* \subseteq L$.
• Can you give a more direct definition of $L'$?

I hope this helps $\ddot\smile$

Answer 2

Try first to figure what $P^*$ means - Some concatenation of words in prime length. Now note that for every $n \geq 2$ we can present him as $n = {p_1}^{a_1} \cdot ... \cdot {p_k}^{a_k}$ so for every $n \geq 2$ you can get that $a^n$ is in $P^*$.

Now we get that $L_1$ is actually every word that doesnt have lone $a$'s inside her - which is easy to identify using automata - whenever you get an $a$ that starts an $a$-sequence you going to a reject state, unless you get another $a$ right away.