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 {a,b} that do not have consecutive a's can be defined by $(emptyset^c\; aa\; emptyset^c)^c$.

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 less-than relation but without the BIT predicate [cite book | last=McNaughton | first=Robert | coauthors = Papert S. | year=1971 | title=Counter-free Automata | publisher=MIT Press | id=ISBN 0-262-13076-9] and as languages definable in linear temporal logic (Kamp).

ee also

*Star height problem
*Generalized star height problem

References

Further reading

*