examples of "interesting" star-free languages Can you point me to some examples (preferably known ones from the literature, but this is not crucial) of "interesting" / non-trivial star-free languages? I'm trying to get some intuitive sense of such languages and what is their power.
 A: Let $A = \{a,b\}$. The following languages are star-fee (in order of difficulty)


*

*Every finite language,

*$a^*$

*$(ab)^*$

*$(ab,ba)^*$

*$(a(ab)^*)b^*$

*$(a(a(ab)^*)b^*)b^*$

*More generally, the languages $D_n$ defined by $D_0 = 1$ and $D_{n+1} = (aD_nb)^*$.


You could also use the following result of [2] to build other examples. A submonoid $M$ of $A^*$ is pure if, for every $u \in A^*$ and every positive $n$, $u^n \in M$ implies $u \in M$. Then

Proposition [Straubing] If $L$ is star-free and $L^*$ is pure, then $L^*$ is star-free.

If you know about logic, another way to built examples is to consider any language defined by a first order formula in the signature $(<, ({\bf a})_{a\in A})$, interpreted on finite words, for instance:


*

*$\exists x\ {\bf a}x$ $\quad$ "There is a position in the word which carries an $a$", defines the language $A^*aA^*$.

*$\neg(\exists x\ \exists y\ (x < y \wedge {\bf a}x \wedge {\bf b}y))$, defines the complement of $A^*aA^*bA^*$.


I let you find the first-order formulas defining the set of all words containing exactly 3 occurrences of the factor $abb$ or at most 2 occurrences of $bbb$ and starting with the prefix $bab$. This language is star-free, because of the following result [1].
Proposition [Mc Naughton]. A language is first-order definable if and only if it is star-free.
You could also use linear temporal logic, which is used in model checking. It has exactly the same expressive power as first order logic and hence defines exactly the star-free languages.
[1] McNaughton, Robert; Papert, Seymour. Counter-free automata. With an appendix by William Henneman. M.I.T. Research Monograph, No. 65. The M.I.T. Press, Cambridge, Mass.-London, 1971. xix+163 pp. 
[2] H. Straubing, Relational morphisms and operations on recognizable sets, RAIRO Inform. Théor. 15 (1981), no. 2, 149--159. 
