go-v.orgcodex
Menu
Page tools

codex · Philosophy

Star height problem

In formal language theory, the star height problem 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? The problem was first introduced by Eggan in 1963.

Wikipedia contributors, "Star height problem", Wikipedia, revision 1371584489, retrieved 20 November 2026, source, CC BY-SA 4.0.

More Philosophy · Search the codex