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. ISBN 978-0-914894-69-8.
↑ Marcel-Paul Schützenberger (1965). "On finite monoids having only trivial subgroups" (PDF). Information and Computation. 8 (2): 190–194. doi:10.1016/s0019-9958(65)90108-7.
↑ 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. Zbl 0816.68086.
↑ McNaughton, Robert; Papert, Seymour (1971). Counter-free Automata. Research Monograph. 65. With an appendix by William Henneman. MIT Press. ISBN 0-262-13076-9. Zbl 0232.94024.
↑ 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. Zbl 1086.68074.
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. ISBN 978-90-5356-576-6.

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 restricted Tree stack 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.

This article is issued from Wikipedia - version of the 10/16/2016. The text is available under the Creative Commons Attribution/Share Alike but additional terms may apply for the media files.

Star-free language

See also

References