Jump to content

Star-free language

From Wikipedia, the free encyclopedia

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". For where , the language can be defined as , taking the set of all words and removing from it words starting with , ending in or containing or . However, when , this definition does not create .

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 the counter-free languages[6] and as languages definable in linear temporal logic.[7]

All star-free languages are in uniform AC0.

See also[edit]


  1. ^ Lawson (2004) p.235
  2. ^ Arto Salomaa (1981). Jewels of Formal Language Theory. Computer Science Press. p. 53. ISBN 978-0-914894-69-8.
  3. ^ Marcel-Paul Schützenberger (1965). "On finite monoids having only trivial subgroups" (PDF). Information and Computation. 8 (2): 190–194. doi:10.1016/s0019-9958(65)90108-7.
  4. ^ Lawson (2004) p.262
  5. ^ Straubing, Howard (1994). Finite automata, formal logic, and circuit complexity. Progress in Theoretical Computer Science. Basel: Birkhäuser. p. 79. ISBN 3-7643-3719-2. Zbl 0816.68086.
  6. ^ McNaughton, Robert; Papert, Seymour (1971). Counter-free Automata. Research Monograph. Vol. 65. With an appendix by William Henneman. MIT Press. ISBN 0-262-13076-9. Zbl 0232.94024.
  7. ^ Kamp, Johan Antony Willem (1968). Tense Logic and the Theory of Linear Order. University of California at Los Angeles (UCLA).