theoretical computer science Theoretical computer science is a subfield of computer science and mathematics that focuses on the Abstraction, abstract and mathematical foundations of computation. It is difficult to circumscribe the theoretical areas precisely. The Associati ...

and

formal language theory In logic, mathematics, computer science, and linguistics, a formal language is a set of string (computer science), strings whose symbols are taken from a set called "#Definition, alphabet". The alphabet of a formal language consists of symbol ...

, 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 match 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 standard set of letter (alphabet), letters written to represent particular sounds in a spoken language. Specifically, letters largely correspond to phonemes as the smallest sound segments that can distinguish one word from a ...

, the

empty word In formal language theory, the empty string, or empty word, is the unique string of length zero. Formal theory Formally, a string is a finite, ordered sequence of characters such as letters, digits or spaces. The empty string is the special cas ...

, the

empty set In mathematics, the empty set or void set is the unique Set (mathematics), set having no Element (mathematics), elements; its size or cardinality (count of elements in a set) is 0, zero. Some axiomatic set theories ensure that the empty set exi ...

symbol, all boolean operators – 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 formalizations of concatenati ...

but no

Kleene star In mathematical logic and theoretical computer science, the Kleene star (or Kleene operator or Kleene closure) is a unary operation on a Set (mathematics), set to generate a set of all finite-length strings that are composed of zero or more repe ...

.Lawson (2004) p.235 The condition is equivalent to having generalized star height zero. For instance, the language

\Sigma^*

of all finite words over an alphabet

\Sigma

can be shown to be star-free by taking the complement of the empty set,

\Sigma^*=\bar

. Then, the language of words over the alphabet

\

that do not have consecutive a's can be defined as

\overline

, first constructing the language of words consisting of

aa

with an arbitrary prefix and suffix, and then taking its complement, which must be all words which do not contain the substring

aa

. An example of a regular language which is not star-free is

(aa)^*

, i.e. the language of strings consisting of an even number of "a". For

(ab)^*

where

a \neq b

, the language can be defined as

\Sigma^* \setminus (b\Sigma^* \cup \Sigma^*a \cup \Sigma^*aa\Sigma^* \cup \Sigma^*bb\Sigma^* )

, taking the set of all words and removing from it words starting with

b

, ending in

a

or containing

aa

bb

. However, when

a = b

, this definition does not create

(aa)^*

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, also called a periodic waveform (or simply periodic wave), is a function that repeats its values at regular intervals or periods. The repeatable part of the function or waveform is called a ''cycle''. For example, the tr ...

syntactic monoid In mathematics and computer science, the syntactic monoid M(L) of a formal language L is the minimal monoid that recognizes the language L. By the Myhill–Nerode theorem, the syntactic monoid is unique up to unique isomorphism. Syntactic quot ...

s.Lawson (2004) p.262 They can also be characterized logically as languages definable in FO the

first-order logic First-order logic, also called predicate logic, predicate calculus, or quantificational logic, is a collection of formal systems used in mathematics, philosophy, linguistics, and computer science. First-order logic uses quantified variables over ...

over the natural numbers with the less-than relation, as languages accepted by some aperiodic finite-state automaton (known as 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 logic, modal temporal logic with modalities referring to time. In LTL, one can encode formula (logic), formulae about the future of path (graph theory), paths, e.g., a c ...

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

Notes

References

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

See also

Notes

References