2
$\begingroup$

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.

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

4 Answers 4

1
$\begingroup$

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

$\endgroup$
2
$\begingroup$

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

$\endgroup$
2
$\begingroup$

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

$\endgroup$
1
$\begingroup$

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

$\endgroup$
5
  • 3
    $\begingroup$ 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)^*$. $\endgroup$ May 3, 2021 at 11:05
  • 4
    $\begingroup$ 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. $\endgroup$ May 3, 2021 at 11:19
  • 1
    $\begingroup$ Thanks for correcting me again :o $\endgroup$
    – nir shahar
    May 3, 2021 at 11:30
  • 1
    $\begingroup$ 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$. $\endgroup$
    – Nathaniel
    May 3, 2021 at 11:34
  • 2
    $\begingroup$ 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). $\endgroup$ May 3, 2021 at 11:35

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.