Star free language vs. regular language

Problem Detail: 

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$
$A\subseteq\Sigma\Rightarrow\Sigma^*A\Sigma^*$ is star-free $\Longrightarrow$
$A\subseteq\Sigma\Rightarrow\ A^*=\overline{\Sigma^*\overline{A}\Sigma^*}$ is star-free

Asked By : Untitled

Answered By : Raphael

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

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

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.)

4. See also here.

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/10768