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, boolean operators 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 X denotes the complement of a subset X of . Marcel-Paul Schützenberger characterized star-free languages as those with aper... more

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, boolean operators 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 X denotes the complement of a subset X of . 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[ less