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?


1 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.
  • $\begingroup$ Thanks. So for L1 I should be able to create a NFA. $\endgroup$
    – darrrrUC
    Commented Sep 7, 2016 at 8:02
  • $\begingroup$ Why do I show that every integer greater than 1 can be written on the form 2m+3n? Thanks $\endgroup$
    – darrrrUC
    Commented Sep 7, 2016 at 8:19
  • $\begingroup$ @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. $\endgroup$ Commented Sep 7, 2016 at 16:26

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .