The generalized star-height problem in
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 ...
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 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 ...
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 character (computing), characters that specifies a pattern matching, match pattern in string (computer science), text. Usually ...
, but they have a built-in complement operator. For a regular language, its
generalized star height 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 Rigour#Mathematics, mathematically rigorous instructions, typically used to solve a class of specific Computational problem, problems or to perform a computation. Algo ...
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
In theoretical computer science and formal language theory, 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 word, the empty set symbol, all boolean o ...
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 minimal monoid that recognizes the language L. By the Myhill–Nerode theorem, the syntactic monoid is unique up to unique isomorphism.
Syntactic quot ...
s. In particular star-free languages are a proper decidable subclass of regular languages.
See also
*
Eggan's theorem and
Generalized star height sections of the
Star height 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