Intheoretical computer science andformal language theory, aregular language is said to bestar-free if it can be described by aregular expression constructed from the letters of thealphabet, theempty word, theempty set symbol, allboolean operators – includingcomplementation – andconcatenation but noKleene star.^[1] The condition is equivalent to havinggeneralized star height zero.

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

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

Marcel-Paul Schützenberger characterized star-free languages as those withaperiodicsyntactic monoids.^[3][4] They can also be characterized logically as languages definable in FO[<], thefirst-order logic over the natural numbers with the less-than relation,^[5] as languages accepted by someaperiodic finite-state automaton (known as counter-free languages),^[6] and as languages definable inlinear temporal logic.^[7]

All star-free languages are in uniformAC⁰.

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

• Lawson, Mark V. (2004).Finite automata. Chapman and Hall/CRC.ISBN 1-58488-255-7.Zbl 1086.68074.
• Diekert, Volker; Gastin, Paul (2008). "First-order definable languages". In Jörg Flum; Erich Grädel; Thomas Wilke (eds.).Logic and automata: history and perspectives(PDF). Amsterdam University Press.ISBN 978-90-5356-576-6.

• Logic in computer science
• Formal languages
• Automata (computation)
• Theoretical computer science stubs

• Articles with short description
• Short description matches Wikidata
• All stub articles