enter image description here

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:enter image description here


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.

  • $\begingroup$ Thanks. Yes. It had confused me, but now I understand it. On the other hand, is $\left\{x^2\right\}$ simply starred? $\endgroup$ – eraldcoil Sep 16 '18 at 3:16
  • $\begingroup$ $\{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. $\endgroup$ – rici Sep 16 '18 at 3:22
  • $\begingroup$ 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 $\endgroup$ – eraldcoil Sep 16 '18 at 3:38
  • 1
    $\begingroup$ 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? $\endgroup$ – theyaoster Sep 16 '18 at 4:06
  • $\begingroup$ 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 $\endgroup$ – eraldcoil Sep 16 '18 at 4:43

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.