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 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 at 9:40
  • $\begingroup$ @nirshahar indeed, that's right $\endgroup$ – jackes gamero May 3 at 9:45
  • $\begingroup$ @Shaull Not entirely, I just wasn't sure if my reasoning was correct. I am sorry ^^" $\endgroup$ – jackes gamero May 3 at 9:46
  • $\begingroup$ @Shaull do i have to delete this post or something? $\endgroup$ – jackes gamero May 3 at 9:47
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$ – Emil Jeřábek May 3 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$ – Emil Jeřábek May 3 at 11:19
  • 1
    $\begingroup$ Thanks for correcting me again :o $\endgroup$ – nir shahar May 3 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 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$ – Emil Jeřábek May 3 at 11:35

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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