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 symb ...
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 c ...
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" or ...
, 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 Computational problem, problems or to perform a computation. Algorithms are used as specificat ...
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 ...
s. The theorem of
Schützenberger 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 zero ...
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