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 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 [math]\displaystyle{ \Sigma^* }[/math] of all finite words over an alphabet [math]\displaystyle{ \Sigma }[/math] can be shown to be star-free by taking the complement of the empty set, [math]\displaystyle{ \Sigma^*=\bar{\emptyset} }[/math]. Then, the language of words over the alphabet [math]\displaystyle{ \{a,\,b\} }[/math] that do not have consecutive a's can be defined as [math]\displaystyle{ \overline{\Sigma^* aa \Sigma^*} }[/math], first constructing the language of words consisting of [math]\displaystyle{ aa }[/math] with an arbitrary prefix and suffix, and then taking its compliment, which must be all words which do not contain the substring [math]\displaystyle{ aa }[/math].
An example of a regular language which is not star-free is [math]\displaystyle{ (aa)^* }[/math],[2] i.e. the language of strings consisting of an even number of "a". For [math]\displaystyle{ (ab)^* }[/math] where [math]\displaystyle{ a \neq b }[/math], the language can be defined as [math]\displaystyle{ \Sigma^* \setminus (b\Sigma^* \cup \Sigma^*a \cup \Sigma^*aa\Sigma^* \cup \Sigma^*bb\Sigma^* ) }[/math], taking the set of all words and removing from it words starting with [math]\displaystyle{ b }[/math], ending in [math]\displaystyle{ a }[/math] or containing [math]\displaystyle{ aa }[/math] or [math]\displaystyle{ bb }[/math]. However, when [math]\displaystyle{ a = b }[/math], this definition does not create [math]\displaystyle{ (aa)^* }[/math].
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
References
- ↑ Lawson (2004) p.235
- ↑ Arto Salomaa (1981). Jewels of Formal Language Theory. Computer Science Press. p. 53. ISBN 978-0-914894-69-8. https://books.google.com/books?id=A-hQAAAAMAAJ.
- ↑ Marcel-Paul Schützenberger (1965). "On finite monoids having only trivial subgroups". Information and Computation 8 (2): 190–194. doi:10.1016/s0019-9958(65)90108-7. http://igm.univ-mlv.fr/~berstel/Mps/Travaux/A/1965-4TrivialSubgroupsIC.pdf.
- ↑ Lawson (2004) p.262
- ↑ 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. https://archive.org/details/finiteautomatafo0000stra.
- ↑ McNaughton, Robert; Papert, Seymour (1971). Counter-free Automata. Research Monograph. 65. With an appendix by William Henneman. MIT Press. ISBN 0-262-13076-9. https://archive.org/details/CounterFre_00_McNa.
- ↑ Kamp, Johan Antony Willem (1968). Tense Logic and the Theory of Linear Order. University of California at Los Angeles (UCLA).
- Lawson, Mark V. (2004). Finite automata. Chapman and Hall/CRC. ISBN 1-58488-255-7.
- Diekert, Volker; Gastin, Paul (2008). "First-order definable languages". in Jörg Flum. Logic and automata: history and perspectives. Amsterdam University Press. ISBN 978-90-5356-576-6. http://www.lsv.ens-cachan.fr/Publis/PAPERS/PDF/DG-WT08.pdf.
 |  |
