Star-free language

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 compliment, 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 the counter-free languages and as languages definable in linear temporal logic.

All star-free languages are in uniform AC⁰.

See also

• Star height
• Generalized star height problem
• 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.