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

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.

• is the language the kleenee-star of $\{w| \space |w| \text{ is prime}\}$? May 3, 2021 at 9:40
• Looks good. Any particular reason that you suspect it's incorrect? (we usually discourage questions of the form "check my answer"). May 3, 2021 at 9:40
• @nirshahar indeed, that's right May 3, 2021 at 9:45
• @Shaull Not entirely, I just wasn't sure if my reasoning was correct. I am sorry ^^" May 3, 2021 at 9:46
• @Shaull do i have to delete this post or something? May 3, 2021 at 9:47

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

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$$.

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)$$).

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!)

• The language just consists of all words of length $\ne1$, thus you can write it even more simply as $\epsilon+(a+b)^2(a+b)^*$. May 3, 2021 at 11:05
• No, it’s not words that are not $\epsilon$. As I already wrote, it’s words of length $\ne1$. $\epsilon$ is in the language. Words of length $\ge2$ are in the language. Words of length $1$ are not in the language, as $1$ is the only nonnegative integer that cannot be written as a (possibly empty) sum of primes. May 3, 2021 at 11:19
• Thanks for correcting me again :o May 3, 2021 at 11:30
• Your regular expression is still wrong, since it includes $a$. Also you don't need to consider $0$ to be prime to have $\varepsilon$ in the language, since by definition of the Kleene star, $\varepsilon \in L$. May 3, 2021 at 11:34
• I’m sorry, but I have to do it again. $\epsilon$ is in the language because it is included in $X^*$ no matter what $X$ is. This has nothing to do with $0$ being prime. Even if $0$ were prime, this would not change the language, thus the second expression is wrong (it actually matches all strings). May 3, 2021 at 11:35

Every integer other than 1 is the sum of primes. So it’s either 0 or >= 2 symbols.

eps + (a+b)(a+b)(a+b)*


One way to prove this is to show that the base language $$L'=\{w∣|w|$$ is prime $$\}$$ is regular. If it is, you can apply the known result that the $$A^*$$ of a regular language $$A$$ is regular.

• It isn’t; that’s the point of the exercise. Dec 13, 2023 at 12:52