# Is (a*b) or (a*b)* star-free?

Here is the proof of a∗ being star-free:

$$\Sigma* = \bar{\emptyset}$$

$$A∗= \overline{Σ∗(Σ∖A)Σ∗}$$

Would this be a proof for $$a * b$$? : $$A∗B= \overline{Σ∗(Σ∖A)Σ∗(Σ∖B)}$$

For $$(A * B )*$$ it seems more complicated if not impossible, but is that proofable?

$$a^*b = (a^*)\cdot b$$
$$(a^*b)^* = \{\varepsilon\} \cup \{a,b\}^* b$$
• Thank you! I forgot that star-free languages are closed regarding boolean operators / concatenation. I assume $\{A,B\}* = \overline{\Sigma*((\Sigma∖A)\cup(\Sigma∖B))\Sigma*}$? If you have time to spare, would you mind telling me whether (a+ b)∗ is non-star free or whether I could alter that grammar easily to obtain a non-star free grammar? More importan: do you know the dot-depth of those two grammars? Do I simply write out the extended form without the star and then count how often boolean expressions and concatenation alternate? I.e. for ab it would be 2 and for (ab)* its 2 or 2.5? Oct 20, 2023 at 1:44
• It seems that $(a^+b)^* = (a^*\cdot ab)^*$ is helpful here. Note that star-free languages are first-order definable, thus "every $b$ is preceded by $a$ and last letter is $b$". I am not familiar enough with dot-depth to answer. Oct 20, 2023 at 11:32