This article will be permanently flagged as inappropriate and made unaccessible to everyone. Are you certain this article is inappropriate? Excessive Violence Sexual Content Political / Social
Email Address:
Article Id: WHEBN0004922792 Reproduction Date:
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^{0}.
Computer science, Automata theory, Formal language, String (computer science), Nondeterministic finite automaton
Turing machine, Theoretical computer science, Formal language, Chomsky hierarchy, Regular grammar
Computer science, Mathematics, Artificial intelligence, Theory of computation, Numerical analysis
Logic, Semantics, String (computer science), Mathematical logic, Computer science
Parsing, Turing machine, Noam Chomsky, Linguistics, Mathematical logic
Automata theory, Nested word, Transition monoid, Regular language, Star-free language
Regular language, Star height, Formal language theory, Kleene star, Algorithm
Mathematics, Automata theory, Semigroup, Positive integer, Monoid