# formal language

## Star height problem ★★

Author(s): Lawrence Eggan C.

**Conjecture**The star height problem in formal language theory is the question whether all regular languages can be expressed using regular expressions of limited star height, i.e. with a limited nesting depth of Kleene stars. Specifically, is a nesting depth of one always sufficient? If not, is there an algorithm to determine how many are required?

Keywords: formal language; Kleene stars; regular expressions; regular languages