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.

• $A^* \not = \Sigma^* A \Sigma^*$ – reinierpost Apr 11 at 9:46
• @reinierpost You are misreading the equation. There are two complement bars on top of $A$ and on top of the whole equation. Sorry, I guess I was not good at formatting in 2013. – Untitled Apr 12 at 15:31
• @reinierpost I edited the post to make it easier to read. Thanks for the feedback. – Untitled Apr 12 at 15:36
• Thanks! Hard to miss now. – reinierpost Apr 13 at 6:35

Regular languages are those that can be described by weak monadic second order logic (WMSO) .

Star-free languages are those that can be described by first order logic with $<$ (FO[<]) .

The two logics are not equally powerful. One example for a language that is WMSO-definable but not FO[<]-definable is $(aa)^*$ (which is clearly regular³); this can be shown using Ehrenfeucht-Fraissé games⁴.

1. Weak Second-Order Arithmetic and Finite Automata by Büchi (1960)
2. Counter-free automata by McNaughton and Papert (1971)
3. A WMSO-formula for $(aa)^*$ is

\ \begin{align} \bigl[ \forall x. P_a(x)\bigr] \land \Bigl[ \exists x. P_a(x) \to \bigl[ \exists X. X(0) &\land [\forall x,y. X(x) \land \operatorname{suc}(x,y) \to \lnot X(y)] \\ &\land [\forall x,y. \lnot X(x) \land \operatorname{suc}(x,y) \to X(y)] \\ &\land [\forall x. \operatorname{last}(x) \to \lnot X(x)] \bigr] \Bigr] \;. \end{align}

(If the word is not empty, $X$ is the set of all even indices.)

• I know what is "monadic" in the logic. Do you happen to know what is the "weak" restriction? – Hendrik Jan Mar 27 '13 at 0:41
• @HendrikJan: It's just that both model and sets have to be finite; MSO deals with infinite words (it corresponds to $\omega$-regular languages, to be precise). – Raphael Mar 27 '13 at 7:58

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[<]), 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).

Star free languages are described by regular expressions that include concatenation, complementation, union, intersection, but no Kleene-star.

Since regular languages are closed under all these operations (where complementation is the crucial point), then every star-free language is also regular.

Perhaps you mean the converse? Are all regular languages star-free? The answer to the latter is no. See this paper for details.

• yes I meant the converse, edited the question. – Untitled Mar 25 '13 at 11:44

A simple separating example is (aa)*. More sophisticated: All binary strings with even (or odd) parity.

• What does this add over the accepted answer? – Raphael Aug 17 '18 at 19:40
• @Raphael The parity example. Though it would be nice if Holger explained why it's not star-free. – David Richerby Aug 18 '18 at 8:42