examples of "interesting" star-free languages

Question

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.

Answer 1

Let $A = \{a,b\}$. The following languages are star-fee (in order of difficulty)

1. Every finite language,
2. $a^*$
3. $(ab)^*$
4. $(ab,ba)^*$
5. $(a(ab)^*)b^*$
6. $(a(a(ab)^*)b^*)b^*$
7. 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:

1. $\exists x\ {\bf a}x$ $\quad$ "There is a position in the word which carries an $a$", defines the language $A^*aA^*$.
2. $\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.