Editing Star height problem (section)

{{Short description|Problem in formal language theory}}

The '''star height problem''' in [[formal language theory]] is the question whether all [[regular language]]s can be expressed using [[Regular expression#Formal language theory|regular expression]]s of limited [[star height]], i.e. with a limited nesting depth of [[Kleene star]]s. Specifically, is a nesting depth of one always sufficient? If not, is there an [[algorithm]] to determine how many are required? The problem was first introduced by Eggan in 1963.{{sfn|Eggan|1963}}