Star-free language

From Wikipedia, the free encyclopedia

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, boolean operators and concatenation but no Kleene star. For instance, the language of words over the alphabet {a,b} that do not have consecutive a's can be defined by .

Marcel-Paul Schützenberger characterized star-free languages as those with aperiodic syntactic monoids. They can also be characterized logically as languages definable in FO[<], the first-order logic over the less-than relation but without the BIT predicate^[1] and as languages definable in linear temporal logic (Kamp).

[edit] See also

• Star height problem
• Generalized star height problem

[edit] References

[edit] Further reading

• Schützenberger M.P. (1965). "On Finite monoids having only trivial subgroups". Information and Computation 8 (2): 190–194. 

v • d • e Automata theory: formal languages and formal grammars Chomsky hierarchy Grammars Languages Minimal automaton Type-0 Unrestricted Recursively enumerable Turing machine n/a (no common name) Recursive Decider Type-1 Context-sensitive Context-sensitive Linear-bounded n/a Indexed Indexed Nested stack n/a Tree-adjoining etc. (Mildly context-sensitive) Embedded pushdown Type-2 Context-free Context-free Nondeterministic pushdown n/a Deterministic context-free Deterministic context-free Deterministic pushdown Type-3 Regular Regular Finite n/a n/a Star-free Aperiodic finite Each category of languages or grammars is a proper subset of the category directly above it; and any automaton in each category has an equivalent automaton in the category directly above it.