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$
$AsubseteqSigmaRightarrowSigma^*ASigma^*$ is star-free $Longrightarrow$
$AsubseteqSigmaRightarrow 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⁴.
- Weak Second-Order Arithmetic and Finite Automata by Büchi (1960)
- Counter-free automata by McNaughton and Papert (1971)
- 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.)
- See also here.
Best Answer from StackOverflow
Question Source : http://cs.stackexchange.com/questions/10768
