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.
[1] The condition is equivalent to having generalized star height zero.
For instance, the language
of all finite words over an alphabet
can be shown to be star-free by taking the complement of the empty set,
Then, the language of words over the alphabet
that do not have consecutive a's can be defined as
, first constructing the language of words consisting of
with an arbitrary prefix and suffix, and then taking its complement, which must be all words which do not contain the substring
An example of a regular language which is not star-free is
,[2] i.e. the language of strings consisting of an even number of "a".
, the language can be defined as
, taking the set of all words and removing from it words starting with
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 languages accepted by some aperiodic finite-state automaton (known as counter-free languages)[6], and as languages definable in linear temporal logic.
[7] All star-free languages are in uniform AC0.
This theoretical computer science–related article is a stub.