Star free language vs. regular language I was wondering, since $a^*$ is itself a star-free language, is there a regular language that is not a star-free language? Could you give an example?



(from wikipdia) Lawson defines star-free languages as:


  A regular language is said to be star-free if it can be described by a regular expression constructed from the letters of the alphabet, the empty set symbol, all boolean operators – including complementation – and concatenation but no Kleene star.




Here is the proof of $a^*$ being star-free:


  $\emptyset$ is star-free $\Longrightarrow$
  $\Sigma^*=\bar{\emptyset}$ is star-free $\Longrightarrow$
  If $A\subseteq\Sigma$ then $\Sigma^*A\Sigma^*$ is star-free $\Longrightarrow$
  If $A\subseteq\Sigma$ then $A^*=\overline{\Sigma^*(\Sigma \setminus A)\Sigma^*}$ is star-free


In the last line we have $A^*=\overline{\Sigma^*(\Sigma \setminus A)\Sigma^*}$, because any word that is not of form $A^*$ contains a letter in $\Sigma \setminus A$ and vice versa.
Schützenberger (1965) gave an algebraic characterization of the star-free languages: a regular language is star-free if and only if its syntactic monoid is aperiodic. Contrary to the logical characterization (star-free = FO[&lt;]), this algebraic characterization gives an algorithm to decide whether a given regular language is star-free (the regular language can be given by a finite automaton, a regular expression or a regular grammar). Using the logical characterization (due to McNaughton and Papert) one can then decide the following problem: given a WMSO formula, is there a FO formula describing the same language? 

M.-P. Schützenberger, On finite monoids having only trivial subgroups, Information and Control 8 (1965), 190-194.

R.~McNaughton and S.~Papert, Counter-free automata, The M.I.T. Press, Cambridge, Mass.-London, 1971.

A full proof of Schützenberger's theorem can be found in various textbooks or survey papers. For an elementary presentation of the corresponding algorithm (without a proof), see 

J.-É. Pin, Finite semigroups and recognizable languages : an introduction, in NATO Advanced Study Institute Semigroups, Formal Languages and Groups, J. Fountain (éd.), 1-32, Kluwer academic publishers, (1995).