|
The generalized star-height problem in formal language theory is the open question whether all regular languages defined by regular expressions that include the complement operator can be expressed using regular expressions (possibly including the complement operator) with a limited nesting depth of Kleene stars. Specifically, it is an open question whether a nesting depth of more than 2 is required, and if so, whether it is possible to determine how many are required.
See also
References
|
