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. For instance, the language of words over the alphabet $\{a,\,b\}$ that do not have consecutive a's can be defined by $(\emptyset ^{c}aa\emptyset ^{c})^{c}$, where $X^{c}$ denotes the complement of a subset $X$ of $\{a,\,b\}^{*}$. The condition is equivalent to having generalized star height zero.

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

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. Zbl 1086.68074.
• Diekert, Volker; Gastin, Paul (2008). "First-order definable languages". In Jörg Flum; Erich Grädel; Thomas Wilke. Logic and automata: history and perspectives (PDF). Amsterdam University Press. ISBN 978-90-5356-576-6.