Star-free language

Remarks

Example: over $\Sigma = \set{a, b}$, the language $(ab)^*$ is star-free, because $$(ab)^* = \Sigma^* \setminus \left( b \Sigma^* \cup \Sigma^* a \cup \Sigma^* aa \Sigma^* \cup \Sigma^* bb \Sigma^* \right),$$ where $\Sigma^* = \Sigma^* \setminus \emptyset$ is star-free by clauses 1 and 3. Indeed, take a nonempty word that does not start with $b$, does not end with $a$ and contains neither $aa$ nor $bb$. It alternates $a$ and $b$, starting with $a$ and ending with $b$. Non-example: over $\set{a}$, the language $(aa)^*$ is regular but not star-free; it cannot be produced by the clauses, as shown by its syntactic monoid $\Z/2\Z$, which is not aperiodic. Every star-free language is regular, since the clauses only use operations under which regular languages are closed.