# 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 set symbol, all boolean operators – including complementation – and concatenation but no Kleene star.[1] For instance, the language of words over the alphabet ${\displaystyle \{a,\,b\}}$ that do not have consecutive a's can be defined by ${\displaystyle (\emptyset ^{c}aa\emptyset ^{c})^{c}}$, where ${\displaystyle X^{c}}$ denotes the complement of a subset ${\displaystyle X}$ of ${\displaystyle \{a,\,b\}^{*}}$. The condition is equivalent to having generalized star height zero.

An example of a regular language which is not star-free is ${\displaystyle \{(aa)^{n}\mid n\geq 0\}}$.[2]

Marcel-Paul Schützenberger characterized star-free languages as those with aperiodic syntactic monoids.[3][4] They can also be characterized logically as languages definable in FO[<], the first-order logic over the natural numbers with the less-than relation,[5] as the counter-free languages[6] and as languages definable in linear temporal logic.[7]

All star-free languages are in uniform AC0.