Star-free language
In
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 .
All star-free languages are in uniform AC0.
See also
Notes
- ^ Lawson (2004) p.235
- ISBN 978-0-914894-69-8.
- .
- ^ Lawson (2004) p.262
- Zbl 0816.68086.
- Zbl 0232.94024.
- ^ Kamp, Johan Antony Willem (1968). Tense Logic and the Theory of Linear Order. University of California at Los Angeles (UCLA).
References
- Lawson, Mark V. (2004). Finite automata. Chapman and Hall/CRC. Zbl 1086.68074.
- Diekert, Volker; Gastin, Paul (2008). "First-order definable languages". In Jörg Flum; Erich Grädel; Thomas Wilke (eds.). Logic and automata: history and perspectives (PDF). Amsterdam University Press. ISBN 978-90-5356-576-6.