Encyclopedia > Star height problem

  Article Content

Star height problem

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 30 years, to be solved by Kosaburo Hashiguchi[?] in 1983. The answer to all questions is yes: Hashiguchi published an algorithm to determine an expression's star height in 1988.

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



All Wikipedia text is available under the terms of the GNU Free Documentation License

 
  Search Encyclopedia

Search over one million articles, find something about almost anything!
 
 
  
  Featured Article
Jamesport, New York

... Hispanic or Latino of any race. There are 605 households out of which 26.1% have children under the age of 18 living with them, 60.7% are married couples living together, ...

 
 
 
This page was created in 19.9 ms