regular languages


Star height problem ★★

Author(s): Lawrence Eggan C.

\begin{conjecture} The \href[star height problem]{http://en.wikipedia.org/wiki/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? \end{conjecture}

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

Syndicate content