Star-free language

Short description: Classification of formal languages

In theoretical computer science and formal language theory, 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 word, the empty set symbol, all boolean operators – including complementation – and concatenation but no Kleene star. The condition is equivalent to having generalized star height zero.

For instance, the language ${\mathrm{\Sigma }}^{*}$ of all finite words over an alphabet $\mathrm{\Sigma }$ can be shown to be star-free by taking the complement of the empty set, ${\mathrm{\Sigma }}^{*}=\overline{\mathrm{\varnothing }}$. Then, the language of words over the alphabet $\{a,b\}$ that do not have consecutive a's can be defined as $\overline{{\mathrm{\Sigma }}^{*}aa{\mathrm{\Sigma }}^{*}}$, first constructing the language of words consisting of $aa$ with an arbitrary prefix and suffix, and then taking its complement, which must be all words which do not contain the substring $aa$.

An example of a regular language which is not star-free is $(aa{)}^{*}$, i.e. the language of strings consisting of an even number of "a". For $(ab{)}^{*}$ where $a\ne b$, the language can be defined as ${\mathrm{\Sigma }}^{*}\setminus (b{\mathrm{\Sigma }}^{*}\cup {\mathrm{\Sigma }}^{*}a\cup {\mathrm{\Sigma }}^{*}aa{\mathrm{\Sigma }}^{*}\cup {\mathrm{\Sigma }}^{*}bb{\mathrm{\Sigma }}^{*})$, taking the set of all words and removing from it words starting with $b$, ending in $a$ or containing $aa$ or $bb$. However, when $a=b$, this definition does not create $(aa{)}^{*}$.

Marcel-Paul Schützenberger characterized star-free languages as those with aperiodic syntactic monoids. They can also be characterized logically as languages definable in FO[<], the first-order logic over the natural numbers with the less-than relation, as languages accepted by some aperiodic finite-state automaton (known as counter-free languages), and as languages definable in linear temporal logic.

All star-free languages are in uniform AC⁰.

It takes non-elementary time to decide whether a star-free language over two letters is

The emptiness problem of starfree language says:

• Input: a string in the symbols of $\{a,b\}$, empty set, concatenation, union, intersection, and complement.
• Output: Whether this language contains any element.

This problem is decidable, but only in nonelementary time. As immediate corollaries, it is decidable but nonelementary to decide whether two starfree languages are equal, are disjoint, or contain one another.

See also

• Star height
• Star height problem
• Generalized star-height problem

References

• Lawson, Mark V. (2004). Finite automata. Chapman and Hall/CRC. ISBN 1-58488-255-7. 
• Diekert, Volker; Gastin, Paul (2008). "First-order definable languages". in Jörg Flum. Logic and automata: history and perspectives. Amsterdam University Press. ISBN 978-90-5356-576-6. http://www.lsv.ens-cachan.fr/Publis/PAPERS/PDF/DG-WT08.pdf.