Decide if a language is regular

Question

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?

Answer 1

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.