star-free language

{{Short description|Classification of formal languages}}

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.Lawson (2004) p.235 The condition is equivalent to having generalized star height zero.

For instance, the language $\backslash Sigma^*$ of all finite words over an alphabet $\backslash Sigma$ can be shown to be star-free by taking the complement of the empty set, $\backslash Sigma^*=\backslash bar\{\backslash emptyset\}$. Then, the language of words over the alphabet $\backslash \{a,\backslash ,b\backslash \}$ that do not have consecutive a's can be defined as $\backslash overline\{\backslash Sigma^*\; aa\; \backslash 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)^*$,{{cite book|author=Arto Salomaa|title=Jewels of Formal Language Theory|url=https://books.google.com/books?id=A-hQAAAAMAAJ|year=1981|publisher=Computer Science Press|isbn=978-0-914894-69-8|page=53}} i.e. the language of strings consisting of an even number of "a". For $(ab)^*$ where $a\; \backslash neq\; b$, the language can be defined as $\backslash Sigma^*\; \backslash setminus\; (b\backslash Sigma^*\; \backslash cup\; \backslash Sigma^*a\; \backslash cup\; \backslash Sigma^*aa\backslash Sigma^*\; \backslash cup\; \backslash Sigma^*bb\backslash 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.{{cite journal | author=Marcel-Paul Schützenberger | author-link=Marcel-Paul Schützenberger | title=On finite monoids having only trivial subgroups | journal=Information and Computation| year=1965| volume=8 | issue=2 | pages=190–194|url=http://igm.univ-mlv.fr/~berstel/Mps/Travaux/A/1965-4TrivialSubgroupsIC.pdf | doi=10.1016/s0019-9958(65)90108-7| doi-access=free }}Lawson (2004) p.262 They can also be characterized logically as languages definable in FO[<], the first-order logic over the natural numbers with the less-than relation,{{cite book | last=Straubing | first=Howard | title=Finite automata, formal logic, and circuit complexity | url=https://archive.org/details/finiteautomatafo0000stra | url-access=registration | series=Progress in Theoretical Computer Science | location=Basel | publisher=Birkhäuser | year=1994 | isbn=3-7643-3719-2 | zbl=0816.68086 | page=[https://archive.org/details/finiteautomatafo0000stra/page/79 79] }} as languages accepted by some aperiodic finite-state automaton (known as counter-free languages),{{cite book | last1=McNaughton | first1=Robert | last2=Papert | first2=Seymour | author2-link=Seymour Papert | others=With an appendix by William Henneman | series=Research Monograph | volume=65 | year=1971 | title=Counter-free Automata | publisher=MIT Press | isbn=0-262-13076-9 | zbl=0232.94024 | url-access=registration | url=https://archive.org/details/CounterFre_00_McNa }} and as languages definable in linear temporal logic.{{cite book | last = Kamp| first=Johan Antony Willem |author-link=Hans Kamp | title = Tense Logic and the Theory of Linear Order| publisher = University of California at Los Angeles (UCLA) | year=1968}}

All star-free languages are in uniform AC⁰.