13
$\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.

Improve this question
$\endgroup$
3
  • $\begingroup$ $A^* \not = \Sigma^* A \Sigma^*$ $\endgroup$
    – reinierpost
    Apr 11, 2019 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, 2019 at 15:31
  • $\begingroup$ @reinierpost I edited the post to make it easier to read. Thanks for the feedback. $\endgroup$
    – Untitled
    Apr 12, 2019 at 15:36

4 Answers 4

Reset to default
12
$\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.
Improve this answer
$\endgroup$
2
  • $\begingroup$ I know what is "monadic" in the logic. Do you happen to know what is the "weak" restriction? $\endgroup$
    – Hendrik Jan
    Mar 27, 2013 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, 2013 at 7:58
15
$\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).

Improve this answer
$\endgroup$
8
$\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.

Improve this answer
$\endgroup$
1
  • $\begingroup$ yes I meant the converse, edited the question. $\endgroup$
    – Untitled
    Mar 25, 2013 at 11:44
2
$\begingroup$

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

Improve this answer
$\endgroup$
2
  • 1
    $\begingroup$ What does this add over the accepted answer? $\endgroup$
    – Raphael ♦
    Aug 17, 2018 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, 2018 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.