Star height problem

HomePage | Recent changes | View source | Discuss this page | Page history | Log in |

Printable version | Disclaimers | Privacy policy

The star-height problem in formal language theory is the question whether all regular languages be expressed using regular expressions with a limited nesting depth of Kleene stars? Specifically, is a nesting depth of more than 2 required? If so, can we determine how many are required? This theoretical problem remained open for 30 years, to be solved by Kosaburo Hashiguchi in 1983. The answer is yes.

The generalized star height problem is the same problem for regular expressions that include the complement operator. This is still an open problem.