principleModerate
Star free language vs. regular language
Viewed 0 times
regularstarlanguagefree
Problem
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.
(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.
Solution
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).
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).
Context
StackExchange Computer Science Q#10768, answer score: 15
Revisions (0)
No revisions yet.