Proving that $L=\{ w \mid \lvert w \rvert$ is prime $\}$* is a regular language

Question

I'm trying to prove that the following languague is a regular language:

$L=\{ w \mid \lvert w \rvert$ is prime $\}$*

What I have thought is to divide each word $w \in L$ into subwords of length 2 if the word is even and and if the word is odd end with a suffix of length 3, in this way I would get the following regular expression:

(aa + ab + ba + bb)* (aaa + aba + abb + aab + baa + bab + bba + bbb + $\epsilon$)

Is my reasoning correct?

Otherwise I would appreciate so much any help.

Answer 1

We are provided the language :

$$L=\{w| |w| \text{ is prime} \}^*$$

Let us investigate the type of strings in $L$. We see that $L$ has such strings whose length is either zero or can be expressed as a sum of prime numbers. i.e. if $x \in L$ then we have :

$$|x| = \begin{cases} 0 \text{ or}\\ \Sigma p_i \text{ where $p_i$ $\in$ Set of all prime numbers}\\ \end{cases}$$

Now let us consider first the set of all strings of even length. i.e. $|x| = 2k , \text{$k \in \mathbb{N}$ and $k\geq 0$}$

So given any string of even length, we can write it as a concatenation of $0$ or more number strings of length $2$, but we see that $2$ is a prime number. So any string of even length $\in L$ and can be expressed by the regular expression : $$((a+b)(a+b))^*$$

From the above expression, we can generate strings of length $0,2,4,...$ $\tag 1$

Let us consider the strings of odd length.

Let us consider the string of length $1$. But $1$ is not a prime number. So strings of length $1$ cannot be present in $L$. So we are left with the odd numbers $3,5,7,...$ or $$|x|= 2\lambda+1, \text{$\lambda \in \mathbb{N}$ and $\lambda\geq 1$} \tag 2$$ $$\implies |x| = 3+ (2\lambda+1 -3) = 3+ (2\lambda -2)=3+ 2(\lambda -1)$$ $$|x| = 3+2\mu \text{ , $\mu \in \mathbb{N}$ and $\mu\geq 0$}$$

Now $3$ and $2$ are prime numbers. So any odd length string of length greater than $1$ can be represented by the concatenation of a string of prime length $3$ followed by zero or more numbers of strings of prime length $2$, which can be represented by the regular expression:

$$(a+b)(a+b)(a+b)((a+b)(a+b))^*$$

From the above two calculations we can say that L:

$$L = ((a+b)(a+b))^*+(a+b)(a+b)(a+b)((a+b)(a+b))^*$$

This is how we suggest that $L$ is a regular language.

Now as far as the language is concerned, we see from $(1)$ and $(2)$ we see that strings in $L$ have lengths $0,2,3,4,5,6,...$, which is simply :

$$L= \epsilon + (a+b)(a+b)(a+b)^*$$

Answer 2

In fact this follows from a general property of the star operation. When we start with an arbitrary language $L$ of all strings of certain lengths, then the star $L^*$ of that language is always regular. More precisely:

Let $A\subseteq \mathbb N$, and $L = \{w\in \Sigma^*\mid |w|\in A\}$. Then $L^*$ is regular.

This is a consequence of a property of unary languages, i.e., languages over a single symbol. See this question: If $L$ is a subset of $\{0\}^∗$ , then how can we show that $L^∗$ is regular?

So for $\Sigma = \{0\}$ the statement above is true. For larger alphabets perform an alphabetic substitution (say $\Sigma = \{a,b\}$, then in a regular expression for $L^*$ replace every $0$ by $(a+b)$).

Answer 3

I let you verify that the submonoid of $(\Bbb N, +)$ generated by $2$ and $3$ is equal to ${\Bbb N} - \{1\}$. It follows that $$ K = \bigl\{w \in A^* \mid |w| = 2 \text{ or } |w| = 3\bigr\}^* = A^* - A $$ Now $K \subseteq L$ and $L \cap A = \emptyset$. Thus $K = L$.

Answer 4

You are correct. However we can simplify this a bit: $\epsilon + (a+b)^2(a+b)^*$.

The language is all words with length $\neq 1$. Thanks to @Emil Jerabek and @Nathaniel for pointing this out in the comments! (and correcting me multiple times!)