Star-free language
   HOME

TheInfoList



OR:

A
regular language In theoretical computer science and formal language theory, a regular language (also called a rational language) is a formal language that can be defined by a regular expression, in the strict sense in theoretical computer science (as opposed to ...
is said to be star-free if it can be described by a
regular expression A regular expression (shortened as regex or regexp; sometimes referred to as rational expression) is a sequence of characters that specifies a search pattern in text. Usually such patterns are used by string-searching algorithms for "find" or ...
constructed from the letters of the
alphabet An alphabet is a standardized set of basic written graphemes (called letters) that represent the phonemes of certain spoken languages. Not all writing systems represent language in this way; in a syllabary, each character represents a syll ...
, the
empty set In mathematics, the empty set is the unique set having no elements; its size or cardinality (count of elements in a set) is zero. Some axiomatic set theories ensure that the empty set exists by including an axiom of empty set, while in other ...
symbol, all boolean operators – including complementation – and
concatenation In formal language, formal language theory and computer programming, string concatenation is the operation of joining character string (computer science), character strings wikt:end-to-end, end-to-end. For example, the concatenation of "sno ...
but no
Kleene star In mathematical logic and computer science, the Kleene star (or Kleene operator or Kleene closure) is a unary operation, either on sets of strings or on sets of symbols or characters. In mathematics, it is more commonly known as the free monoid c ...
.Lawson (2004) p.235 For instance, the language of words over the alphabet \ 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 \^*. The condition is equivalent to having
generalized star height In theoretical computer science, more precisely in the theory of formal languages, the star height is a measure for the structural complexity of regular expressions and regular languages. The star height of a regular ''expression'' equals the maxim ...
zero. An example of a regular language which is not star-free is \, i.e. the language of strings consisting of an even number of "a".
Marcel-Paul Schützenberger Marcel-Paul "Marco" Schützenberger (24 October 1920 – 29 July 1996) was a French mathematician and Doctor of Medicine. He worked in the fields of formal language, combinatorics, and information theory.Herbert Wilf, Dominique Foata, ''et al.' ...
characterized star-free languages as those with
aperiodic A periodic function is a function that repeats its values at regular intervals. For example, the trigonometric functions, which repeat at intervals of 2\pi radians, are periodic functions. Periodic functions are used throughout science to desc ...
syntactic monoid In mathematics and computer science, the syntactic monoid M(L) of a formal language L is the smallest monoid that recognizes the language L. Syntactic quotient The free monoid on a given set is the monoid whose elements are all the strings of zero ...
s.Lawson (2004) p.262 They can also be characterized logically as languages definable in FO the
first-order logic First-order logic—also known as predicate logic, quantificational logic, and first-order predicate calculus—is a collection of formal systems used in mathematics, philosophy, linguistics, and computer science. First-order logic uses quantifie ...
over the natural numbers with the less-than relation, as the
counter-free language An aperiodic finite-state automaton (also called a counter-free automaton) is a finite-state automaton whose transition monoid is aperiodic. Properties A regular language is star-free if and only if it is accepted by an automaton with a finite and ...
s and as languages definable in linear temporal logic. All star-free languages are in uniform AC0.


See also

* Star height *
Generalized star height problem The generalized star-height problem in formal language theory is the open question whether all regular languages can be expressed using generalized regular expressions with a limited nesting depth of Kleene stars. Here, generalized regular expres ...
* Star height problem


References

* * Logic in computer science Formal languages Automata (computation) {{comp-sci-theory-stub