# Simply starred language. $\left\{(ab)^n:n\in\mathbb{N}\right\}$ it is regular?

I have many doubts with this. First: In the definition, let $A=\left\{x\right\}$ one-letter alphabet. Then $A^{\ast}$ is simply starred?

Second: In the definition, I know that $\left\{a^nb^n: n \in \mathbb{N} \right\}$ is not regular (because of the Pumping lemma) but $\left\{a^nb ^n: n \in\mathbb{N}\right\}$ is it simply starred anyway?

On the other hand, I know that if $r$ regular expression, then $L(r)$ is regular and so $(L(r))^{\ast}$ is regular. But if we start from $A=\left\{ab\right\}$ with $ab$ string, then $L(ab)$ is regular so $(L(ab))^{\ast}$ is regular and $(L(ab))^{\ast}=\left\{ab\right\}^{\ast}=\left\{(ab)^n:n\in\mathbb{N}\right\}$ is not regular, a contradiction. What is wrong?

pd:

## 1 Answer

Yes, $x^*$ is simply starred (for a fixed string $x$) since all star operations in the expression are applied directly to a single string. So is $(ab)^*$ for the same reason. Some more examples (assuming $a,b,c,d,e,f,g$ are strings or characters):

• $a^*b^*c^*$ is simply starred.
• $a(bc)^*d + efg^*$ is simply starred.
• $a(b + c)d + e + fg$ is simply starred.
• $(a + b)^*$ is not simply starred.
• $(a^*b^*)^*$ is not simply starred.

Note, however, that the language of a regular expression which is not simply starred may actually be simply starred. This is because a language may be expressed by a different regular expression which is simply starred. For instance, $(a^*)^*$ is not simply starred, but its language is, since $L((a^*)^*) = L(a^*)$.

You are correct in stating that $\{a^nb^n : n \in \mathbb{N}\}$ is not regular. It is not simply starred because by definition, the term "simply starred" is used to describe regular languages.

Your last statement claims that $\{(ab)^n : n \in \mathbb{N}\}$ is not regular, when in fact it is. Are you perhaps confusing $(ab)^n$ with $a^nb^n$ here? They mean very different things.

Edit: I slightly misunderstood Definition 1.3.3; I have removed my bad example.

• Thanks. Yes. It had confused me, but now I understand it. On the other hand, is $\left\{x^2\right\}$ simply starred? – eraldcoil Sep 16 '18 at 3:16
• $\{x^2\}$ has no stars at all so any statement about it of the form "all star closures are $P$" is trivially true. Hence, yes it is. – rici Sep 16 '18 at 3:22
• Is it true that if $L_1$, $L_2$ are simply starred, so is the union $L_1\cup L_2$ and intersection $L_1\cap L_2$? I ask this because I do not fully understand the definition of simply starred – eraldcoil Sep 16 '18 at 3:38
• I misunderstood the definition of simply starred at first, so I have now amended my answer to reflect the correct definition. Does it help clear things up? – theyaoster Sep 16 '18 at 4:06
• I still do not understand the all well definition. For example, the book gives the following example: ¿It is $(x^3\cup x^4)^{\ast}$ simply starred?? I ask, because the book gives it as an example of the above. That is, it is an example of a language simply starred and ${\ast}$-closed but it can not be left as a single regular expression – eraldcoil Sep 16 '18 at 4:43