Star height problem
From Free net encyclopedia
The star-height problem in formal language theory is the question whether all regular languages can 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 25 years until it was solved by Kosaburo Hashiguchi. The answer to all questions is yes: Hashiguchi published an algorithm to determine an expression's star height in 1988.
Also see generalized star height problem.
[edit]
