11
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ $A^* \not = \Sigma^* A \Sigma^*$ $\endgroup$ – reinierpost Apr 11 at 9:46
  • $\begingroup$ @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. $\endgroup$ – Untitled Apr 12 at 15:31
  • $\begingroup$ @reinierpost I edited the post to make it easier to read. Thanks for the feedback. $\endgroup$ – Untitled Apr 12 at 15:36
  • $\begingroup$ Thanks! Hard to miss now. $\endgroup$ – reinierpost Apr 13 at 6:35
11
$\begingroup$

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.
$\endgroup$
  • $\begingroup$ I know what is "monadic" in the logic. Do you happen to know what is the "weak" restriction? $\endgroup$ – Hendrik Jan Mar 27 '13 at 0:41
  • 1
    $\begingroup$ @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). $\endgroup$ – Raphael Mar 27 '13 at 7:58
14
$\begingroup$

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

$\endgroup$
7
$\begingroup$

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.

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

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

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.