This page uses content from Wikipedia and is licensed under CC BY-SA.
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 that do not have consecutive a's can be defined by , where denotes the complement of a subset of . The condition is equivalent to having generalized star height zero.
An example of a regular language which is not star-free is .
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 AC0.
|P ≟ NP||This theoretical computer science–related article is a stub. You can help Wikipedia by expanding it.|