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 } {displaystyle {a,,b}} that do not have consecutive a's can be defined by ( ∅ c a a ∅ c ) c {displaystyle (emptyset ^{c}aaemptyset ^{c})^{c}} , where X c {displaystyle X^{c}} denotes the complement of a subset X {displaystyle X} of { a , b } ∗ {displaystyle {a,,b}^{*}} . The condition is equivalent to having generalized star height zero. 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 } {displaystyle {a,,b}} that do not have consecutive a's can be defined by ( ∅ c a a ∅ c ) c {displaystyle (emptyset ^{c}aaemptyset ^{c})^{c}} , where X c {displaystyle X^{c}} denotes the complement of a subset X {displaystyle X} of { a , b } ∗ {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 { ( a a ) n ∣ n ≥ 0 } {displaystyle {(aa)^{n}mid ngeq 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 AC0.