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

286 Views Asked by At

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

1

There are 1 best solutions below

12
On BEST 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.