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 set symbol, all boolean operators – including complementation – and concatenation but no Kleene star.^[1] For instance, the language of words over the alphabet \{a,\,b\} that do not have consecutive a's can be defined by (\emptyset^c aa \emptyset^c)^c, where X^c denotes the complement of a subset X of \{a,\,b\}^*. The condition is equivalent to having generalized star height zero.

An example of a regular language which is not star-free is \{(aa)^n \mid n \geq 0\}.^[2]

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

References

^ Lawson (2004) p.235
^ Arto Salomaa (1981). Jewels of Formal Language Theory. Computer Science Press. p. 53.
^
^ Lawson (2004) p.262
^ Straubing, Howard (1994). Finite automata, formal logic, and circuit complexity. Progress in Theoretical Computer Science. Basel: Birkhäuser. p. 79.
^ McNaughton, Robert;
^

Lawson, Mark V. (2004). Finite automata. Chapman and Hall/CRC.
Diekert, Volker; Gastin, Paul (2008). "First-order definable languages". In Jörg Flum; Erich Grädel; Thomas Wilke. Logic and automata: history and perspectives (PDF). Amsterdam University Press.

Automata theory: formal languages and formal grammars

Chomsky hierarchy	Grammars	Languages	Abstract machines

Type-0 — Type-1 — — — — — Type-2 — — Type-3 — —	Unrestricted (no common name) Context-sensitive Positive range concatenation Indexed — Linear context-free rewriting systems Tree-adjoining Context-free Deterministic context-free Visibly pushdown Regular — Non-recursive	Recursively enumerable Decidable Context-sensitive Positive range concatenation^* Indexed^* — Linear context-free rewriting language Tree-adjoining Context-free Deterministic context-free Visibly pushdown Regular Star-free Finite	Turing machine Decider Linear-bounded PTIME Turing Machine Nested stack Thread automaton — Embedded pushdown Nondeterministic pushdown Deterministic pushdown Visibly pushdown Finite Counter-free (with aperiodic finite monoid) Acyclic finite

Each category of languages, except those marked by a ^*, is a proper subset of the category directly above it. Any language in each category is generated by a grammar and by an automaton in the category in the same line.

Categories

This article was sourced from Creative Commons Attribution-ShareAlike License; additional terms may apply. World Heritage Encyclopedia content is assembled from numerous content providers, Open Access Publishing, and in compliance with The Fair Access to Science and Technology Research Act (FASTR), Wikimedia Foundation, Inc., Public Library of Science, The Encyclopedia of Life, Open Book Publishers (OBP), PubMed, U.S. National Library of Medicine, National Center for Biotechnology Information, U.S. National Library of Medicine, National Institutes of Health (NIH), U.S. Department of Health & Human Services, and USA.gov, which sources content from all federal, state, local, tribal, and territorial government publication portals (.gov, .mil, .edu). Funding for USA.gov and content contributors is made possible from the U.S. Congress, E-Government Act of 2002.

Crowd sourced content that is contributed to World Heritage Encyclopedia is peer reviewed and edited by our editorial staff to ensure quality scholarly research articles.

By using this site, you agree to the Terms of Use and Privacy Policy. World Heritage Encyclopedia™ is a registered trademark of the World Public Library Association, a non-profit organization.

Star-free language