The generalized star-height problem in
formal language theory
In logic, mathematics, computer science, and linguistics, a formal language consists of words whose letters are taken from an alphabet and are well-formed according to a specific set of rules.
The alphabet of a formal language consists of sy ...
is the open question whether all
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 ...
s can be expressed using generalized regular expressions with a limited nesting depth of
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 ...
s. Here, generalized regular expressions are defined like
regular expressions
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" o ...
, but they have a built-in complement operator. For a regular language, its
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 ...
is defined as the minimum nesting depth of Kleene stars needed in order to describe the language by means of a generalized regular expression, hence the name of the problem.
More specifically, it is an open question whether a nesting depth of more than 1 is required, and if so, whether there is an
algorithm
In mathematics and computer science, an algorithm () is a finite sequence of rigorous instructions, typically used to solve a class of specific problems or to perform a computation. Algorithms are used as specifications for performing ...
to determine the minimum required star height.
[Sakarovitch (2009) p.171]
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 ...
s of star-height 0 are also known as
star-free language 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 K ...
s. The theorem of
Schützenberger Schützenberger may refer to these people:
* Anne Ancelin Schützenberger (1919–2018) (de)
* Paul Schützenberger, French chemist
* René Schützenberger, French painter
* Marcel-Paul "Marco" Schützenberger, French mathematician and Doctor of M ...
provides an algebraic characterization of star-free languages by means of aperiodic
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. In particular star-free languages are a proper decidable subclass of regular languages.
See also
*
Eggan's theorem and
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 ...
sections of the
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 ...
article
*
Star height problem
The star height problem in formal language theory is the question whether all regular languages can be expressed using regular expressions of limited star height, i.e. with a limited nesting depth of Kleene stars. Specifically, is a nesting depth ...
References
*
*
*
*
*
External links
Jean-Eric Pin: The star-height problem
Formal languages
Unsolved problems in computer science
Automata (computation)
{{comp-sci-theory-stub