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?


1 Answer 1


$a^*b = (a^*)\cdot b$

$(a^*b)^* = \{\varepsilon\} \cup \{a,b\}^* b$

  • $\begingroup$ 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? $\endgroup$
    – Crea Teeth
    Oct 20, 2023 at 1:44
  • $\begingroup$ 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. $\endgroup$ Oct 20, 2023 at 11:32

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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