Star-free language explained

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

\Sigma ^{*} of all finite words over an alphabet \Sigma can be shown to be star-free by taking the complement of the empty set, \Sigma ^{*=\bar{\emptyset}} . Then, the language of words over the alphabet \{a,b\} that do not have consecutive a's can be defined as \overline{\Sigma ^{*} aa \Sigma ^{*}} , first constructing the language of words consisting of aa with an arbitrary prefix and suffix, and then taking its complement, which must be all words which do not contain the substring aa .

An example of a regular language which is not star-free is

(aa) ^{*} ,^[2] i.e. the language of strings consisting of an even number of "a". For (ab) ^{*} where a ≠ b , the language can be defined as \Sigma ^{*} \setminus (b\Sigma ^{*} \cup \Sigma ^{*a} \cup \Sigma ^{*aa\Sigma} ^{*} \cup \Sigma ^{*bb\Sigma} ^{*} ) , taking the set of all words and removing from it words starting with b , ending in a or containing aa or bb . However, when a = b , this definition does not create (aa) ^{*} .

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 AC⁰.

See also

• Star height
• Star height problem
• Generalized star-height problem

References

• Book: Lawson, Mark V. . Finite automata . Chapman and Hall/CRC . 2004 . 1-58488-255-7 . 1086.68074 .
• Book: Jörg Flum . Erich Grädel . Thomas Wilke . Logic and automata: history and perspectives . 2008 . Amsterdam University Press . 978-90-5356-576-6 . First-order definable languages . Volker . Diekert . Paul . Gastin .

Notes and References

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