Regular language union non-regular language

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^*$?

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$

• It helps but I am still confused :) Is however I try to draw a DFA for primes using combinations $a^2$ and $a^3$ (since every prime can be described with a combination of $2n+3m$) I can allways sneak in a non-prime to get to acceptance since I can allso easily describe $a^4$ the same way. – darrrrUC Sep 7 '16 at 14:05
• @darrrrUC Ok, let me check one thing – please answer these two questions: does or does not $a^4 \in L'$, does or does not $a^4 \in L$? – dtldarek Sep 7 '16 at 14:22
• $a^4$ is in neither, but could I not create it with a string such as $a^2$ $a^2$ Or is that just an invalid string since it adds to a $a^4$? Thank you for your patience :) – darrrrUC Sep 7 '16 at 14:38
• What i ment is that $a^5$ is in $L$ and that is $a^2 + a^3$ ? – darrrrUC Sep 7 '16 at 14:39
• @darrrrUC Check out the examples section: Kleene star. – dtldarek Sep 7 '16 at 15:59

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.

• In order to write $a^n$ as a concatenation of words of the form $a^p$ with $p$ prime, you need to express $n$ as a sum of primes, not a product. This is possible for $n \geq 2$ since then $n$ is a sum of $2$'s and possibly a $3$. – marlu Sep 7 '16 at 11:22
• multiplication and power are actually a lot of additions, so it doesnt matter. However, I do agree that what you suggested would be more simple to understand. – Snufsan Sep 7 '16 at 11:24