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

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

, 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 oth ...

symbol, all

boolean operators Boolean operation or Boolean operator may refer to: * Boolean function, a function whose arguments and result assume values from a two-element set ** Boolean operation (Boolean algebra), a logical operation in Boolean algebra (AND, OR and NOT) ** B ...

– including complementation – and

concatenation In formal language theory and computer programming, string concatenation is the operation of joining character strings end-to-end. For example, the concatenation of "snow" and "ball" is "snowball". In certain formalisations of concatenat ...

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

.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

\^*

. The condition is equivalent to having generalized star height 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 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 ...

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

over the natural numbers with the less-than relation, as the counter-free languages and as languages definable in

linear temporal logic In logic, linear temporal logic or linear-time temporal logic (LTL) is a modal temporal logic with modalities referring to time. In LTL, one can encode formulae about the future of paths, e.g., a condition will eventually be true, a condition will ...

. All star-free languages are in uniform AC⁰.

References

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

See also

References