# Decide if a language is regular

I have to decide for two languages if they are regular or not, I have

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

$L_2 = (P\{b\})^*$

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

All languages are over $\Sigma = \{a,b\}$

My question is if any of these can be regular since I somehow have to keep count over the number of $a's$ in $P$?

If they can be regular any pointers on why or how to start creating a DFA for it would be much appriciated. Lets say I would create a DFA for $L_2$ then $a$ would have to loop back to itself and only move forward when $b$ is entered, that would accept a string such as $"aab"$ since "aa" is prime. but what if we enter 4 a's? $"aaaab"$ this would not conform to $p$.

Im a bit confused here as to how to make a DFA in this case (if it can be done at all.) Or could I simply use $P = \{a^p | p = prime\}$ as a transition itself?

HINT: You can use the pumping lemma to show that $L_2$ is not regular. If $n$ is the pumping length, let $p\ge n$ be prime, and start with the word $a^pb\in L_2$.
$L_1$ is a bit trickier.
• Show that every integer greater than $1$ can be written in the form $2m+3n$ for some non-negative integers $m$ and $n$.
Let $L$ be the language corresponding to the regular expression $aaa^*$, i.e., $L=\{a^n:n\ge 2\}$.
• Show that $L_1=(L\cup\{b\})^*$, and conclude that $L_1$ is regular.
• @darrrrUC: Yes, for $L_1$ it’s not even hard to design a DFA. You need the $2m+3n$ result in order to show that whenever $n\ge 2$, the string $a^n$ is a concatenation of strings of prime length. Commented Sep 7, 2016 at 16:26